题目:http://poj.org/problem?id=3273
二分枚举,据说是经典题,看了题解才做的,暂时还没有完全理解。。
#include <stdio.h>
#include <string.h> int n, m;
int a[]; bool judge(int x)
{
int money = , cnt = ;
for(int i = ; i < n; i++)
{
if(money + a[i] <= x)
money += a[i];
else
{
money = a[i];
cnt++;
}
}
if(cnt > m)
return ;
else return ;
} int main()
{
int low = , high = ;
scanf("%d %d", &n, &m);
for(int i = ; i < n; i++)
{
scanf("%d", &a[i]);
if(low < a[i])
low = a[i];
high += a[i];
}
int mid = (low + high) / ;
while(low < high)
{
if(judge(mid))
high = mid - ;
else low = mid + ;
mid = (low + high) / ;
}
printf("%d\n", mid);
return ;
}