Description

Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤ money_i ≤ 10,000) that he will need to spend each day over the next N (1 ≤ N ≤ 100,000) days.

FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤ N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.

FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit.

Input

Output

Sample Input

7 5100400300100500101400
Sample Output
500
Hint
If Farmer John schedules the months so that the first two days are a month, the third and fourth are a month, and the last three are their own months, he spends at most $500 in any month. Any other method of scheduling gives a larger minimum monthly limit.
Source
USACO 2007 March Silver
題目意思：
給出John在N個月中每個月的花費，John想將N個月分成M個組。每組的月份是連續的，同一組的花費被相加起來，求所有分組情況中最高花費的最低值。
解題思路：
二分法，所求答案ans在[low,high]范圍內二分。low是最高的單月花費；high是各個月所有花費之和，mid是當前的ans。遍歷各個月份，將花費總和不超過ans的月份歸入一個組，統計在當前ans情況下能分成幾個組。如果組數少于M，說明ans偏大，范圍變成前二分之一；否則說明ans偏小，范圍變成后二分之一。
#include<iostream>#include<cstdio>#include<iomanip>#include<cmath>#include<cstdlib>#include<cstring>#include<map>#include<algorithm>using namespace std;#define MAXN 100000int a[MAXN];int n,m,high=0,low=-1,mid;bool solve(){    int res=1,sum=0;    for(int i=0; i<n; ++i)    {        sum+=a[i];//若干月花費總和        if(sum>=mid)//超過限額        {            ++res;//分組數目            if(sum==mid) sum=0;//當前月花費計入當前組            else sum=a[i];//當前月花費計入下一組            if(i==n-1) --res;//最后一個月剛好被計入最后一組        }    }    if(res>m) return false;    else return true;}int main(){#ifdef ONLINE_JUDGE#else    freopen("F:/cb/read.txt","r",stdin);    //freopen("F:/cb/out.txt","w",stdout);#endif    ios::sync_with_stdio(false);    cin.tie(0);    cin>>n>>m;    for(int i=0; i<n; ++i)    {        cin>>a[i];        if(a[i]>low) low=a[i];//最高的單月花費        high+=a[i];//所有花費之和    }    while(low<high)    {        mid=0.5*(low+high);        if(solve()) high=mid-1;        else low=mid+1;    }    cout<<low<<endl;    return 0;}/*7 5100400300100500101400*/