2013年8月13日 星期二

2013/8/13 TIOJ 1432 骨牌遊戲

// http://218.210.35.237:8080/JudgeOnline/showproblem?problem_id=1432
#include <iostream>
#include <cstdio>
using namespace std;
int n, w; int num[1001];
bool test(int op)
{
    int sum = 0; int wi = w;
    for(int i = 0; i < n; i++)
    {
        sum += num[i]; if( num[i] > op ) return 0;
        if( sum > op ){ sum = num[i]; wi--; }
        if( wi < 0 ) return 0;
    }
    return 1;
}
int main()
{


    while( scanf("%d %d", &n, &w) )
    {
        if( n == 0 && w == 0 ) break;
        int sum = 0;

        for(int i = 0; i < n; i++)
            {scanf("%d", &num[i]); sum+=num[i]; }

        int l = 0; int r = sum+1;

        while( l != r-1 )
        {
            int mid = (l+r)/2;
            if( test(mid) == 1 ) r = mid;
            else l = mid;
        }
        printf("%d\n", r);
    }
}

沒有留言:

張貼留言