又又又又是二分啦

憨憨桃子又来啦

题目链接：monthly expense

题目描述：

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.

输入：

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

输出：

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

就是有n天的花费，要把它划分成m个月，求最大花费的最小值。

这个题和河中跳房子那道题就很像啦

河中跳房子问题题解

注意

1.low应该为日花费中的最大值，high等于总共的花费。

2.用一个变量统计几天的总花费，当花费大于mid时，num++,当num<=m时，说明mid取大了，此时更改high的值（这里一定要注意！！num小的时候是mid大了！！！划重点！）

代码实现

#include<stdio.h>int main(){int n,m,i,low=0,high=0,mid,a[100010];scanf("%d %d",&n,&m);for(i=0;i<n;i++){scanf("%d",&a[i]);if(low<a[i]) low=a[i];high+=a[i]; }while(low<high){mid=(low+high)/2;int num=1,sum=0;for(i=0;i<n;i++){if(sum+a[i]<=mid) sum+=a[i];else{sum=a[i];num++;}}if(num<=m) high=mid-1;else low=mid+1;}printf("%d\n",high);return 0;}