【POJ - 3273】Monthly Expense （二分）

sky-stars 2019-08-04 原文

【POJ – 3273】Monthly Expense （二分）

Monthly Expense

直接上中文

Descriptions

给你一个长度为N的序列，现在要让你把他们切割成M份（所以每一份都是连续的），然后每一份都有一个和sum[i]，其中最大的一个是maxSum = max(sum[i]),问这个最大值最小是多少？

输入

多组输入输出
每组数据第一行是2个整数N,M（1<=M<=N<=100000），接着是N行，每行一个整数vi，表示这个序列.

输出

每组数据输出一行一个数，为这个最大值最小是多少

输入样例

7 5
100
400
300
100
500
101
400

输出样例

500

样例解释

对于样例，你可以把100,400分成第一组，300,100分成第二组，500分成第三组，101分成第四组，400分成第五组,他们的和最大的是500。

题目链接

https://vjudge.net/problem/POJ-3273

一开始上届是n个数的和。代表只分一组。

下届是n个数中最大的数。代表分n组；

如果结果是mid=（上届+下届）/2；那么根据mid看看能分多少组。组数大于m，代表mid比实际值小。下届变成mid+1。否则，上届变成mid-1；

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 100000+5
using namespace std;
int N,M;
int l,r,mid;//左右中
int a[Maxn];//序列
int solve()
{
    mid=(l+r)/2;//预判的最大值
    int sum=0;//当前这份的和
    int cnt=1;//有cnt份
    for(int i=0; i<N; i++)
    {
        if(sum+a[i]<=mid)//当前这份的和不能大于预判的最大值
            sum+=a[i];
        else
        {
            sum=a[i];
            cnt++;
        }
        if(cnt>M)//所得份数大于题目要求的份数，即预判和小了
            return 0;
    }
    return 1;//所得份数小于等于题目要求的份数，即预判和大了
}
int main()
{
    while(cin>>N>>M)
    {
        l=r=0;//初始化
        for(int i=0; i<N; i++)
        {
            cin>>a[i];
            l=max(l,a[i]);
            r+=a[i];
        }
        while(l<=r)
        {
            if(!solve())//预判和小了，整个取值区间要变大，即左区间向右移动
               l=mid+1;
            else//预判和大了，整个取值区间要变小，即右区间向左移动
                r=mid-1;
        }
        cout<<mid<<endl;
    }
}