二分法找答案——YCOJ月度开销题解

题目描述：

Description

农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。

约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。

约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。

Input

第一行包含两个整数N,M，用单个空格隔开。

接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。

Output

一个整数，即最大月度开销的最小值。

Sample Input 1

7 5

100

400

300

100

500

101

400

Sample Output 1

500

题解：

​ 二分法的题目答案通常不太方便直接求，所以可以通过二分法确定范围，最后确定答案。

​ 这道题对最大月度开销进行二分，初始范围可以直接设为 1- 1e9，设 ok(x) 为每个fajo月的花费都不超过x的可行度的布尔值，每次二分都算一次 ok(mid) ，因为题目求的是最大月度开销的最小值，所以如果返回1，说明最小值应在l~mid范围内继续查找，而如果返回0，说明最小值肯定比mid大，则应在mid+1~r内继续查找。

​ ok(x)这个方法可以通过for循环简单遍历一遍实现。每个fajo月肯定是连续的几天，用一个sum变量储存一个fajo月的开销，如果还没超出x,则把下一天的开销也累加进来，直到超出x，便把sum归零，重新计下个fajo月。如果月数超过题目中的M，那肯定不存在一个x的值使得每一组的开销都不超过x，返回0。至于小于M则不用返回0，因为可以减少每月的花费来增加月数到M。

​ 下面附上代码：

#include <iostream>
using namespace std;
int N,M;
int k[100010];
bool ok(int x) {             //判断每个fajo月的花费是否都不超过x
 	int sum=0,tot=0;
 	for(int i=1;i<=N;i++) {
 		sum+=k[i];
 		if(sum>x || i==N) {
 			sum=k[i];tot++;
 		}
 		if(tot>M || k[i]>x) {
 			return false;
 		}
 	}
 	return true;
}
int main() {
 	cin >> N >> M;
 	for(int i=1;i<=N;i++) cin >> k[i];              //输入
 	int l=0,r=1e9,mid;
 	while(r-l>1) {                                 //二分
 		mid=(l+r)/2;
 		if(ok(mid)) r=mid;
 		else l=mid;
 	}
 	if(!ok(r)) cout << l << endl;
 	else cout << r << endl;
 	return 0;
}

题库链接：http://120.77.248.79/problem/z0114 （注：请不要直接ctrl-c + ctrl-v，管理员会看代码）