# POJ 3273 Monthly Expense (二分)

Monthly Expense

 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 24265 Accepted: 9436

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 ≤ moneyi ≤ 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

Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 contains the number of dollars Farmer John spends on the ith day

Output

Line 1: The smallest possible monthly limit Farmer John can afford to live with.

Sample Input

7 5
100
400
300
100
500
101
400

Sample Output

500

### 思路

• 我们所求出的最大段和一定大于等于当前所有的数，因为这个数一定存在于某个段中
• 如果只分一段，那么段和便是所有数的和，也同时是所有分法段和的最大值

### AC代码

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

using namespace std;

int data[110000];
int n,m;
bool judge(int mid) //判断当前最大段和范围内能否成功分区
{
int now=0,count=1;
for(int i=0; i<n; i++)
{
now+=data[i];
if(now>mid) //当前段已充满，开启下一段
{
now=data[i];
count++;
}
}
return count<=m;    //充满的段小于m没有关系，因为我们可以把已有的段拆开
}
void binary(int low,int high)
{
int ans=0;
while(low<=high)
{
int mid=(low+high)/2;
if(judge(mid))ans=mid,high=mid-1;
else low=mid+1;
}
printf("%d\n",ans);
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
int maxx=0,sum=0;
for(int i=0; i<n; i++)
{
scanf("%d",data+i);
maxx=max(data[i],maxx); //分别求得段和的最小值与最大值
sum+=data[i];
}
binary(maxx,sum);   //在这个区间内二分
}
return 0;
}