POJ-3273 Monthly Expense(二分,花费)

http://poj.org/problem?id=3273

题意：

给出n天中每天的花费，需要将这些天分成m组，每组包含连续的一天或多天，若定义第i组的花费为Ki，求一种分组方法使得K=max{Ki}最小。

输入数据第一行为两个整数n,m，之后给出n个整数代表每天的花费，输出一行表示K

思路：

K的花费必定介于n组花费的最大值，与n组总和值之间，进行二分判断即可。

用已知值去试是否符合当前需求，

代码：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iomanip>
#include<algorithm>
#include<string.h>
#include<queue>
#include<cmath>

using namespace std;
const int maxn=1e5+10;
const int inf=1e10;
typedef long long ll;

int n,m;
int a[maxn];

int check(int top)
{
    int num=1;
    int cur=0;
    for(int i=0; i<n; i++)
    {
        if(cur+a[i]<=top) cur+=a[i];
        else
        {
            num++;
            cur=a[i];
        }
    }
    return num<=m;
}

int main()
{
    while(cin>>n>>m)
    {
        int ma=0,sum=0;
        for(int i=0; i<n; i++)
        {
            cin>>a[i];
            sum+=a[i];
            ma=max(ma,a[i]);
        }

        int low=ma,high=sum;
        int ans=0;

        while(low<=high)
        {
            int mid=(low+high)>>1;
            if(check(mid))
            {
                ans=high;
                high=mid-1;
            }
            else low=mid+1;
        }

        printf("%d
",ans);
    }
    system("pause");
    return 0;
}