【c++（2）】二分3---二分答案

【c++（2）】二分3---二分答案

哈罗，我们继续学习二分的内容。

我们二分可以在数组中进行查找，也可以在各种结构内进行查找，难道我们的二分只能用在查找上么？

我们这节课就来学习进阶的二分。

---

二分解决问题
二分不仅可以二分位置，还可以解决一些实际问题。
【*1下界】
二分答案的下界的概念是：最大的尽量小
我们在前面的下界是：

while(l < r)
{
	
	int m = (l + r) / 2;
	if (a[m] <= x) l = m + 1;
	else r = m;
	
}
return l;

现在我们怎样来检验它是否满足要求呢？这个我们就需要一个子程序来检验情况。
【*2】下界例题
(1)
等级：菜鸟级
星级：3星
知识点：二分下界

Farmer John是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算并记录下了接下来 N (1 ≤ N≤ 100,000) 天里每天需要的开销。Farmer John打算为连续的M(1 ≤ M≤ N) 个财政周期创建预算案，他把一个财政周期命名为一个fajo月。每个fajo月包含一天或连续的多天，每天都被恰好包含在一个fajo月里。

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

这道题我们可以把代码分成几个部分哈，1.check检查函数
2.输入
3.二分+check检验
现在我们来看看怎么写，首先是第1部分，check检查函数，这也是代码最核心的部分。
我们想一下，加入我们现在假设答案是x，也是check传的参数。如果是x，我们怎样来检验x是否成立呢？

既然x是开销最大的月，那么我们可以定义一个money变量来存放每个月的开销，在定义一个cnt来存放有多少个fajo月。
最后满足cnt<=m。
我们既然知道了这些，当然代码就可以写出来。x是最大的开销，所以money不大于x就继续存放，否则就cnt++;并将money设为w[i]。
所以cheak就是：

bool cheak (int x)
{

	int cnt = 1, mny = 0;
	for (int i = 1; i <= n; i++)
	{
		if(mny + w[i] > x){
			cnt++;
			mny = w[i];
		}
		else mny += w[i];
	}
	return cnt <= m;

}

第2部分输入就很简单了吧，cin+for完事。
第三部分二分+cheak检验，这个也算是非常重要的。这道题是最少，所以如果check成功了，那就需要在往小的找。
否则，就1就l=m+1往大的找。
还有一个问题，就是l和r怎样找呢？
其实就是两个极端情况。
如果开销最少，那么每个fajo月就只包含一天，那么最少就要每天开销最多那天的金额。l就是最少。
r呢？如果开销最多，当然就是所有开销的总和啦！
注意：r需要++，就像前面的n+1
代码：
（注意：定义的中间值不能命名为m，因为前面定义了。

while (l < r)
{

	int mid = (l + r) / 2;
	if (cheak (mid)) r = mid;
	else l = mid + 1;

}
cout << l;

把他拼接一下，总的代码：

#include 

using namespace std;
int a[100010], n, mins, maxs, m;
bool cheak (int x){
	int cnt = 1,mny = 0;
	for (int i = 1; i <= n; i++)
	{
		if(mny + a[i] > x)
		{
			cnt++;
			mny = a[i];
		}
		else mny += a[i];
	}
	return cnt <= m;
}

int main(){


	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> a[i];
	for (int i = 1; i <= n; i++)mins = max (mins, a[i]);
	for (int i = 1; i <= n; i++)maxs += a[i];
	int l = mins, r = maxs;
	r++;
	while(l < r)
	{
	
		int mid = (l + r) / 2;
		if (cheak(mid)) r = mid;
		else l = mid + 1;
	
	}
	cout << l;


	return 0;
}

【*3上界】
上界与下界相反，是最小的尽量大。我们就可以把r=m和l=m+1调换一下就可以了。
例题：

每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远(1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间，有N (0 ≤ N ≤ 50,000) 个岩石，每个岩石与起点的距离分别为Di (0 < Di < L)。

在比赛过程中，奶牛轮流从起点出发，尝试到达终点，每一步只能从一个岩石跳到另一个岩石。当然，实力不济的奶牛是没有办法完成目标的。

农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移，看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行，他感到非常厌烦。他计划移走一些岩石，使得从起点到终点的过程中，最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。

请帮助约翰确定移走这些岩石后，最长可能的最短跳跃距离是多少？

等级：中级
星级：3.5星
知识点：二分上界

重要的还是check，首先搞定lr
最小值：如果一个石头都不移除时，岩石间的最短距离，如上例中的2。
最大值：当所有石头都被移除后，可以取得最大值L（河的宽度）。
现在写一下check：
对于答案x，在确保所有区间都>=x的前提下，计算需要移除多少石头。如果移除
的石头数量<=m, 那么表示答案x可行。
check:

bool cheak (int x)
{
	int p = 0, cnt = 0;
	for (int i = 1; i <= n + 1; i++)
	{
		if (a[i] - p < x) cnt++;
		else p = a[i];
	}
	return cnt <= m;
}

下面的代码应该也不用我写了吧