2015年7月30日 星期四

2015/07/30 Codeforces 551C. GukiZ hates Boxes

/*
    顯然要二分搜
    判斷的方式是greedy
    也很直覺啊 就不證了(被打
*/
// http://codeforces.com/problemset/problem/551/C
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

int N, M;
int A[200000];

bool test(ll p)
{
    int _A[200000];

    for(int Ni = 1; Ni <= N; Ni++)
        _A[Ni] = A[Ni];

    int cnt = 0; ll step = 0;

    for(int Ni = 1; Ni <= N; Ni++)
    {
        while( _A[Ni] )
        {
            if( Ni > p ) return false;

            if( step == 0 ) cnt++, step = p-Ni;
            if( cnt > M ) return false;

            ll mn = min((ll)_A[Ni], step);
            _A[Ni] -= mn, step -= mn;
        }

        if( step ) step--;
    }

    return true;
}

int main()
{
    scanf("%d %d", &N, &M);

    for(int Ni = 1; Ni <= N; Ni++)
        scanf("%d", &A[Ni]);

    ll l = -1, r = 1e15;

    while( l+1 != r )
    {
        ll mid = (l+r)/2;

        if( test(mid) ) r = mid;
        else l = mid;
    }

    cout<<r<<endl;
}

沒有留言:

張貼留言