Boxes Packing [Codeforces Round #515 (Div. 3) D]

http://codeforces.com/contest/1066/problem/D

N個の物体があり、重さはA[i]である。
重さK分入る箱がM個ある。
　
物体を左から順に箱詰めするが、以下のルールで箱詰めする。

• 箱詰め前に左から任意の個数捨てる
• 捨てた後、順番に箱に入れていく
• 入れれるだけ入れて、入らなくなったら次の箱に入れる
• M個の箱で残りの全てを入れなくてはいけない

物体を最大何個入れられるか

前提知識

• 二分探索

解法

http://codeforces.com/contest/1066/submission/44198286

二分探索をする。
check(st) := st番目から箱に詰めはじめて、残りを全て箱に入れられるか
これは単調性を持つので、これで箱に全て入れられる最小のst（=ok）が得られる。
すると、あとは、N-okが答え。
　
check関数はシミュレートして箱に入れていけばいい。

int N, M, K, A[201010];
//---------------------------------------------------------------------------------------------------
int check(int st) {
    int cnt = 0;
    int tot = 0;
    rep(i, st, N) {
        if (K < A[i]) return 0;
        if (K < tot + A[i]) {
            cnt++;
            tot = 0;
        }
        tot += A[i];
    }
    cnt++;
    return cnt <= M;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    rep(i, 0, N) cin >> A[i];

    int ng = -1, ok = N;
    while (ng + 1 != ok) {
        int md = (ng + ok) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }
    cout << (N - ok) << endl;
}