B - Friends and Candies

cpcodeforcesdiv3greedymath

最終更新日

Table of Contents

Loading...

問題

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; }