Codeforces Round #307 (Div. 2) C. GukiZ hates Boxes

Codeforces Round #307 (Div. 2)には参加してません。
D難しいですね。

問題

Problem - 551C - Codeforces

解法

基本的には二分探索です。ある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;
}