Codeforces Round #307 (Div. 2) C. GukiZ hates Boxes
Codeforces Round #307 (Div. 2)には参加してません。
D難しいですね。
解法
基本的には二分探索です。あるxが与えられた時,x秒以内に箱をすべて取り除くことができるかを判定します。
基本的にm人の生徒はある規則にしたがって貪欲に動けば良いです。具体的には,
まず1番目にある箱をすべて取り除こうとする。
次に2番目にある箱をすべて取り除こうとする。
...
このようにして箱をすべて取り除けたらx秒以内にすべての箱を取り除けたらOKです。
このxがOKかどうかのチェックはO(n+m)で行うことが出来ます。
const int MAXN = 100010; int n, m, last; ll a[MAXN], b[MAXN]; bool ok(ll x) { int cur = 1; for (int i = 1; i <= n; i++) b[i] = a[i]; for (int i = 0; i < m; i++) { ll tmp = x-cur; while (1) { ll cost = min(tmp, b[cur]); b[cur] -= cost; tmp -= cost; if (b[cur] == 0) { cur++; if (cur == last+1) return true; tmp--; } if (tmp <= 0) break; } } return false; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; if (a[i]) last = i; } ll low = 0, high = 1e16; while (high - low > 1) { ll med = (high+low) / 2; if (ok(med)) high = med; else low = med; } cout << high << endl; return 0; }