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