poj3273 Monthly Expense 二分查找

题目链接

题意：给出n组数据，每组有一个数，有多种方法通过将连续的几组数据并为一组使得组数从n减少至k，每组数据的值为其组中数据之和，每种方法得到的k组数据都有最大的一组数据和m，求这些方法中最小的m

解法：二分查找

以n组中最小的数为左边界l，n组数据之和为右边界r进行二分查找，取中间值mid=(l+r)/2,mid即为k组数据中最大的一组数据和，若mid可将n组数据分成多于k组数据，则mid偏小取右间，

若可将n组数据分成小于k组数据，则mid偏小取左区间，若恰好可分成k组数据，因要取最小的mid所以继续取左区间直都l=r;

#include
#include
#include
#define ll long long
using namespace std;
ll n,m,a[100005];
ll r,l,mid;
bool judge(ll d){
    ll t=0,sum=a[0];
    for(int i=1;id) return 1;
     sum+=a[i];
     if(sum>d){
        sum=a[i];
        t++;
     }
    }
    if(sum) t++;
    return t>m;
}
int bfind(){
while(l>n>>m){
    r=0,l=1<<30;
    for(int i=0;i