我通过了这题,但为什么过了?
把所有数按颜色分成三组。
我开始的时候想着全是偶数个显然答案是 0, 否则肯定是两种颜色奇数个一种颜色偶数个。
那么就给奇数个的颜色分开来,然后找出用一组中和另外一组中最相近的,求出它们差的绝对值作为答案。
显然这样是错的,因为可以在偶数个组里选出两个去和奇数组的对掉。一个很简单的改进想法就是在两个奇数组中分别找出一个和偶数组中最相近的,然后将答案相加来更新答案。
可这样似乎会出错,万一两个奇数组找出来的最接近的是同一个怎么半。
但我一直构造不出反例,于是在最后时刻赌了一把,写了并交了,结果居然过了。
所以这为什么是对的,或者怎么卡掉?