AtCoder ABC 313 C - Approximate Equalization 2 (茶色, 400 点)

ちゃんと証明しないと、なかなか安心して提出できない系

• 問題へのリンク

問題概要

整数列 が与えられる。次の操作を繰り返し行って、 の最大値と最小値の差が 1 以下となるようにしたい。実現のための操作の最小回数を求めよ。

• を選んで、 に 1 を足し、 から 1 を引く

制約

• 

考えたこと：最終形

「最大値と最小値の差が 1 以下」とは、均等にすることを意味する。たとえば、 の要素数が 、総和が であれば、

なので、操作後の配列を としたとき、順番を無視すれば ( が 個) となる。基本的には、「最大値と最小値が 1 以下」である状態とは、この並び替えしかない。

の各要素に対して、 のどの要素を割り当てるのが最適化かを考える問題となる。

小さいものに小さいものを割り当てる

まず、操作前の の要素の並びは全く関係ないのでソートして考えることにする。たとえば

を考えよう。これは均等にすると となる。実は、

• 小さい には、小さい を
• 大きい には、大きい を

割り当てるのが最適となる。つまり、A も B もソートして、その差の和を求めて、2 で割れば OK

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;
    long long S = 0;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        S += A[i];
    }
    sort(A.begin(), A.end());
    
    long long q = S / N, r = S % N;
    vector<long long> B(N);
    for (int i = 0; i < N; ++i) B[i] = q + (i < r);
    sort(B.begin(), B.end());
    
    long long res = 0;
    for (int i = 0; i < N; ++i) res += abs(A[i] - B[i]);
    cout << res/2 << endl;
}