Educational Codeforces Round 3 C – Load Balancing

链接: https://codeforces.com/contest/609/problem/C

public class TaskC {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int[] ary = in.readIntArray(n);
        long res = 0;
        Arrays.sort(ary);
        int sum = 0;
        for (int i:ary) {
            sum+=i;
        }
        for (int i = 0; i < n/2; i++) {
            int b = sum / (n - i);
            res += Math.abs(ary[i] - b);
            sum -= b;
        }
        out.print(res);
    }
}

公式推导题, 先要排序ary, 然后算出数组的和sum. 然后可以观察到, 我们可以把相对大的数给相对小的数以便于达到平衡, 这种平衡有两个可能性, 一种是两数合为奇数, 比如数组 1 2 4, 4+1=5, 5是奇数, 这种情况下给完后的差是1, 即2 2 3, 3-2=1. 另外一种情况是两数合为偶数, 比如 1 2 3, 3+1=4, 4是偶数. 这种情况下给完后的差是0, 即2 2 2, 2-2=0. 所以可以证明这种先排序后两端互相给的方法, 是答案要的方法, 即miimize(Ma – Mb), where a is the most loaded server and b is the least loaded one.

最后我们需要找到平衡数组b, 通过观察我们知道, 我们只需要遍历一半的数组就可以得到答案, 因为我们是通过”给数”的方法, 所以我们用一个循环遍历一半的数组. 通过再次观察不难发现, 比如数组 1 2 3 4 的平衡数组是2 2 3 3 (4给1 1次). 这个平衡数组的sum是1+2+3+4 = 10. 如果我们把10均分, 那么久变成10/4 = 2, 10 mod 4 = 2, 这里的意思是平衡数组中绝大部分是10/4 = 2, 其中有10 mod 4个数比其他数多1. 再举例, 1 2 3 4 5, sum = 15. 15/5 = 3, 15 mod 5 = 0 (整除). 这里说明它的平衡数组是 3 3 3 3 3, 有0个(没有)数比其他数多1. 现在我们验证一下, 5给1 两次, 数组变成 3 2 3 4 3, 4 给2 一次变成3 3 3 3 3. 结束

上面的code并不是这个答案的code. 上面的code用了一个更好的数学方法. 通过上面的观察可以看出, ary的数字a是由两部分组成, 一个数组的均值(sum/n)+多的1(如果有). 这个题问的是第二部分数字的合, 我们现在已知前边两个部分 那么只需要用数字ary[i] – 当前数组的均值sum/n, 即Math.abs(ary[i] – b), 然后不要忘了计算下一个数字均值的时候, 应该减去当前的均值.