[ABC227] D - Project Planning
[Q] https://atcoder.jp/contests/abc227/tasks/abc227_d
K=3の場合を考察し、法則を見つける。
1. Aを昇順sort。上位3つを選ぶ。
2. 下位の値を、上位3つに振り分けることを考える。
3. にぶたんで、最大プロジェクト数を探索する。
Q. K=3
3 5 5 5 を考える。
sortして 3 5 5 5
これは、
3 5 5 5
-------
- 1 1 1 0
- 1 0 1 1
- 1 1 0 1
-------
0 3 3 3
にしたあと、3 回とるのが最適だなと思う。
逆に、
3 5 5 5
=======
->1 // ふりわける
--->1
----->1
=======
0 6 6 6 として、上位 3 つにバランスよく分ければいいと思う。
Q. K=3
1 1 1 1 1 1 10 を考える。
なんとなく、
1 1 1 1 1 1 10
----------------
- 1 1 0 0 0 0 1
- 0 0 1 1 0 0 1
- 0 0 0 0 1 1 1
----------------
0 0 0 0 0 0 7
3 が解答になりそう。
1. 上位3(K)と、それ以外の余剰ポイントを考える。
1 1 1 1 1 1 10
1 1 10 = A[]
1 1 1 1 = 4point
4point は、A[]のどこにでも振り分けられる。
2. にぶたん
作れるプロジェクト数 mid を探索する。
1) mid = 5 だとしたら、
5 5 5
- 1 1 10
------
4 4 0 // 8point 不足
8point > 4point なので、5 プロジェクトは不成立。
2) mid = 3 だとしたら、
3 3 3
- 1 1 10
------
2 2 0 // = 4point 不足
4point不足は補えるので、3 プロジェクトは成立。
そして解答は3。実装
int main(){
cincout();
ll N, K;
cin >> N >> K;
vector<ll> A(N);
rep(i, N) cin >> A[i];
sort(all(A));
ll smalls = 0;
rep(i, N-K){
smalls += A[i]; // 振り分けられるポイント
}
ll B[K]; // 上位K項目
rep(i, K) B[i] = A[N-1-i];
// にぶたん
ll low = -1;
ll high = oo+100;
while (high-low > 1){
ll mid = (high+low)/2;
ll use = 0;
bool ok=true;
rep(i, K){
use += max(0LL, mid-B[i]);
if (use>smalls) ok = false;
}
if (ok) low = mid;
else high = mid;
}
cout << low << endl;
}