二分 boj1461手抄代码

手抄代码Submit: 352   Accepted:98Time Limit: 15000MS  Memory Limit: 65535KDescription
校 内赛马上开始了，选手门比赛时，需要打印代码，但是912的打印机被wangkun弄坏了，无法进行打印。wangkun的钱都上交给wmz了，他只有想 办法让912的小盆友们手抄代码，然后送给选手们。这里共有n份代码 ，编号1,2,…,n。每份代码有pi页。全部分给m个小盆友。每人分到顺序连续的若干份，每份代码只分给一人。 为了和谐，wangkun需要你，求一种方案，使每人分到的页数总和的最大值为最小.

Input
每行输入两个n,m （1<=n<=200） 接下来有n个数，是每份代码的页数。 m < n 当 n = 0 并且 m=0时结束。

Output
输出一行，为每人分到的页数总和的最大值为最小的数.

Sample Input

9 3
100 200 300 400 500 600 700 800 900
0 0

Sample Output

1700

Hint
n=9,m=3
100 200 300 400 500 / 600 700 / 800 900


最开始考虑用dp，未果
考虑到该题具有单调性，即若最大值中的最小值A满足条件(可以分配给m个人)，则>A的所有值也能满足条件，这时就应该寻找更小的A值来满足条件。所以可以二分寻找最合适的值

#include <stdio.h>

int n, m, pages[210];

int check(int mid)
{
    int i, cnt, sum;

    cnt = sum = 0;
    for (i=0 ; i<=n ; i++)
    {
        sum += pages[i];
        if (sum >= mid)
        {
            if (sum > mid)
                i--;
            sum = 0;
            cnt++;
            if (cnt == m)
                break;
        }
    }
    if (i == n || i == n + 1)
        return 0;
    else
        return 1;
}

void solve()
{
    int low, high, mid, i;

    low = high = 0;
    for (i=1 ; i<=n ; i++)
        high += pages[i];

    low = high / n;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (0 == check(mid))
            high = mid - 1;
        else
            low = mid + 1;
    }

    /*特别注意这里，结果应该是low值，因为如果之前已找到答案A, high = mid - 1，最后mid和high值都小于答案，只有在最后一次判断的时候low = mid + 1才再次回到这个答案*/
    printf("%d\n", low);
}

int main(int argc, char *argv[])
{
    int i;
    while (scanf("%d %d", &n, &m))
    {
        if (0 == n && 0 == m)
            break;

        for (i=1 ; i<=n ; i++)
            scanf("%d", &pages[i]);
        
        solve();
    }
}