#include <stdio.h>
#include <string.h>

int n, m;			//把n天分成m组
int money[100000];	//每天的钱数

//假设答案是mid，验证是否正确
//为了便于说明，设正确答案为ans
bool judge(int mid)
{
	//sum表示一组的花费，cnt表示分的组数
    int sum = 0, cnt = 1;
    for(int i = 0; i < n; i++)
    {
    	//因为假设答案是mid，所以当sum + money[i] <= mid时，第i天可以分到上一组中。
    	//这一点很显然，剩下的天数少了，ans当然会更优
        if(sum + money[i] <= mid)
            sum += money[i];

		//如果第i天不能分到上一组，那么只能再分下一组了，这时组数+1
        else
        {
            sum = money[i];
            cnt++;
        }
    }
    //如果分的组数>m，显然这时假设的答案mid太小了，所以mid要增大
    if(cnt > m)
        return 0;

	//否则cnt<=m。
	//如果cnt<m，根据上面说的单调关系，分更多的组ans会更优，即mid<ans
	//如果cnt==m，说明此时可以在分m组的情况下ans<=mid，这时继续尝试在[low,mid]寻找ans
    else
    	return 1;
}

int main()
{
    int low = 0, high = 0;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++)
    {
    	//输入每天的花费，计算low和high
        scanf("%d", &money[i]);
        if(low < money[i])
            low = money[i];
        high += money[i];
    }

    //二分寻找答案，循环在low==high时结束，这时low和high的值都是答案，输出其中一个就可以
    while(low < high)
    {
    	//设答案是mid
    	int mid = (high + low) / 2;
        if(judge(mid))
            high = mid;/*这里有一点不理解，为什么网上大多数代码写的high=mid-1也是正确的，
            			如果是在judge中提到的cnt==m的情况，那么ans是<=mid的啊，为什么ans所
            			在的区间可以跳过mid这个点呢？请知道的回复我，谢谢。*/
        else
        	low = mid + 1;
    }
    //输出high也可以
    printf("%d\n", low);
    return 0;
}

• 不知道为什么排版很乱，在CodeBlocks明明排好版的。复制到IDE中看的清楚些。。谢谢 (45) wolfred7464 2013-10-15 20:52:46