B - Friends and Candies

問題

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

問題文

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

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

$k$ の最小値は？

制約

• $1 \le t \le 10^4$
• $1 \le n \le 2 \times 10^5$
• $0 \le a_i \le 10^4$
• $n$ の総和は $2 \times 10^5$ を超えない

サンプル

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

考察

全員等しく配れない = $\sum a_i$ が $n$ で割り切れないなら、-1 で終わり。

そうではない場合、平均値 = $\frac{\sum a_i}{n}$ になるように配る。
回収する人は、$\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;
}