首先要有一个直觉:我们将A排序之后,为了减少“贫富差距”,我们一定是将A的左边一部分元素都加上K,右边一部分元素都减去K。为什么左边那部分一定都是加上K,而不是加减交错呢?比如说,a<b<c,如果我们决策是 a+K, b-K, c+K 的话,b和c之间的差距不仅没有减小反而被拉大了。所以在最终的方案里,绝对不可能出现“加,减,加”交错操作的情况,唯一的方案就是:左边一部分加K,右边一部分减K。
那么如果确定这个分界线呢?其实并没有更优秀的办法,挨个尝试就行了。假设这个分界线在A[i]后面,也即是说A[0]~A[i]都是加K,A[i+1]~A[n-1]都是减K,那么这个新数组B的最大值,其实可以从左右两部分分别的最大值得到,即MAX = max(A[i]+K, A.back()-K)
.同理,这个新数组B的最小值,其实可以从左右两部分分别的最小值得到,即MIN = min(A[0]+K, A[i+1]-K)
。而我们的答案就是在所有的diff=MAX-MIN
中挑选最小的那个。