POJ 3273 Monthly Expense 二分枚举

题目: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 ;
}
上一篇:java并发系列(六)-----Java并发:volatile关键字解析


下一篇:Java获得文件的创建时间(精确到秒)