問題
https://codeforces.com/contest/1538/problem/B (新しいタブで開く)
問題文
人いて、それぞれ 個のキャンディーを持っている。
全員が同じ数のキャンディーを持つようにしたい。
そのために以下の操作を 1 回だけ行う。
を選び、任意の 人を選ぶ。
その 人のキャンディーを全部回収する。
回収したキャンディーを 1 つずつ、誰か選んで配る。これは回収した 人のうちから選んでもいい。
の最小値は?
制約
- の総和は を超えない
サンプル
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
考察
全員等しく配れない = が で割り切れないなら、-1
で終わり。
そうではない場合、平均値 = になるように配る。
回収する人は、 より大きい人を選ぶ。
これが明らかにベスト。
コード
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; }