（POJ3273）Monthly Expense 二分法 + 贪心

本文主要是介绍（POJ3273）Monthly Expense 二分法 + 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Monthly Expense
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
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

题意：
有一个大小为n的int数组，现在要将它分为连续的m段，问这m段的和的最大值的最小值为多少？

分析：
当m够大时，题目的解就是数组的最大元素值maxa。
当m很小时，题目的解可能是数组所有元素之和sum。
而答案一定在【maxa,sum】之间，所以我们可以用二分查找的方法来快速的找出答案。
如何判断某个值是否成立呢？
例如:x,看x是否成立就是看可以将数组分为和<=x的段数cnt,看cnt是否<=m.
关于求段数cnt，直接用贪心的思想：从头到位扫一遍，加起来比x小就放在这一段，否则就另起一段。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;const int maxn = 100010;
int a[maxn];
int n,m;int binarysearch(int low,int high)
{int mid;while(low <= high){mid = (low + high) / 2;int sum = 0,cnt = 1;for(int i=0;i<n;i++){if(sum + a[i] <= mid)sum += a[i];else{sum = a[i];cnt++;}}if(cnt > m)low = mid + 1;else high = mid - 1;}return low;
}int main()
{int maxa,sum;while(scanf("%d%d",&n,&m)!=EOF){maxa = 0; sum = 0;for(int i=0;i<n;i++){scanf("%d",&a[i]);sum += a[i];maxa = max(maxa,a[i]);}printf("%d\n",binarysearch(maxa,sum));}return 0;
}