B - Friends and Candies

cpcodeforcesdiv3greedymath

最終更新日

問題

https://codeforces.com/contest/1538/problem/B (新しいタブで開く)

問題文

nn 人いて、それぞれ aia_i 個のキャンディーを持っている。
全員が同じ数のキャンディーを持つようにしたい。
そのために以下の操作を 1 回だけ行う。

kk を選び、任意の kk 人を選ぶ。
その kk 人のキャンディーを全部回収する。
回収したキャンディーを 1 つずつ、誰か選んで配る。これは回収した kk 人のうちから選んでもいい。

kk の最小値は?

制約

サンプル

5
4
4 5 2 5
2
0 4
5
10 8 5 1 4
1
10000
7
1 1 1 1 1 1 1
2
1
-1
0
0

考察

全員等しく配れない = ai\sum a_inn で割り切れないなら、-1 で終わり。

そうではない場合、平均値 = ain\frac{\sum a_i}{n} になるように配る。
回収する人は、ain\frac{\sum a_i}{n} より大きい人を選ぶ。
これが明らかにベスト。

コード

https://codeforces.com/contest/1538/submission/125441522 (新しいタブで開く)

なぜか二分探索してるけど、制約的にしなくても間に合うはず。ソートもしなくていいはず。

void solve() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  ll sum = 0;
  rep(i, n) {
    cin >> a[i];
    sum += a[i];
  }
  if (sum % n != 0) {
    cout << -1 << endl;
    return;
  }
  ll avg = sum / n;
  sort(a.rbegin(), a.rend());
  ll ok = n, ng = -1;
  while (abs(ok - ng) > 1) {
    ll mid = (ok + ng) / 2;
    if (a[mid] <= avg) {
      ok = mid;
    }
    else {
      ng = mid;
    }
  }
  cout << ok << endl;
  return;
}