C. Load Balancing

1500
  • Quiz
  • AC
  • 解説
    • sum%N!=0の時のみ説明します
  • 嘘解法
  • コーナー（？）ケース
    • 4 3 2 4
    • この場合、4から1つ動かして、2を3にする必要がある。嘘解法では解=0となってしまう
  • 解法
    • a, a+1がそれぞれ最終形でいくつずつになるかが決まる
    • 上から削って穴を埋めていくのは嘘解法と同じだが、a+1の高さで残してきた数をオーバーしそうな時は調整する
    • 私の場合はa+1が十分出現したあとはa--として基準を1下げて対応した（コード参照）
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    VI A(N);
    rep(i, N) cin >> A[i];
    
    ll sum=SUM(A);
    if(sum%N==0){
      ll mean = sum/N;
      ll ans=0;
      for(ll a : A){
        if(a>mean){
          ans += a-mean;
        }
      }
      p(ans);return 0;
    }

    // 割り切れないとき、a, a+1に別れる
    ll up = sum/N + 1;
    // up側に残せる数
    ll rest = sum%N;

    ll ans=0;
    for(ll a : A){
      if(a>=up){
        ans += a-up;
        rest--;
        if(rest==0)up--;
      }
    }
    p(ans);
    
    return 0;
}