整数二分习题：c++实现：洛谷-2678跳石头，acwing-1227分巧克力，730机器人跳跃(含思路详解，及注意点解释)

这道题是说，有n个石头，最多移走m个石头(m是我们自主输入的，相当于已知的)，求得最短跳跃距离的最大值。也就是我们的主体是两个石头之间的距离，求这个距离的最大值，也就是求 在满足移走<=m的条件下，找到最后一个<=两个石头之间的距离 (提前设定的一个未知数，这个未知数所具有的性质是：是两个石头之间的距离的最小值) ，找到了最后一个最小的距离，也就是得到了最小距离的最大值。

bing的叙述: 在移走不超过M块岩石的情况下，两个相邻岩石之间最短跳跃距离的最大值。我们可以通过二分答案来解决这个问题。我们设定一个未知数，表示两个相邻岩石之间最短跳跃距离的最小值，然后在满足移走不超过M块岩石的条件下，找到最后一个小于等于这个未知数的数，这样就能得到最小跳跃距离的最大值。

好啦，相信仔细想一想，看着图中的描述肯定可以理解啦。是有点难理解的，接下来几道题的思路和这个都差不多。

！注意点：

千万要注意，由于我们在check函数中遍历的是两个石头之间的距离，由于题目中输入的 n 个石头，并不包括起点和终点，所以，我这里把下标为 0 的表示的是起点岩石，下标为 n+1 的表示为终点岩石，且 a[n+1]表示的是起点到终点的距离为length，当我们进行遍历的时候，都是判断当前岩石与前一个岩石的距离，所以check中的循环条件应该从 1 - n+1 。

视频讲解推荐

下面这个视频是b站上一个老师讲的，我感觉讲的非常详细 (而且字很好看，观感良好放心食用)，只是按照他最后的代码我一直有一组测试数据过不了，然后我发现问题就出在我上面写的这个注意点上，也就是n - n+1这两块石头之间的距离没有遍历，改正之后的代码是正确且可以通过的。所以一定要注意这个点。

http:////www.bilibili.com/video/BV1rA4y1o7Dv?vd_source=02dfd57080e8f31bc9c4a323c13dd49c

代码实现

#include<iostream>
using namespace std;
const int N=50010;
int length,n,m,a[N];

bool check(int x){
//遍历所有两石头间的距离，确保x是最小距离
	int start=0,count=0;//最开始的位置 就是与起点石头的距离，所以start初始值为0
	for(int i=1;i<=n+1;i++){
		if(a[i]-start<x)count++;
		else start=a[i];//更新起始位置
	}
	return count<=m;
}

int find(int l,int r){
//会有很多满足<=m条件的最小距离，但我们要通过二分来找到最后一个满足<=m条件的最小距离，即最小距离的最大值
	while(l<r){
		int mid=(l+r+1)>>1;
		if(check(mid)){
			l=mid;
		}
		else r=mid-1;
	}
	return l;
}
int main()
{
	cin>>length>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	a[n+1]=length;
	int ans=find(0,length);//最小距离的初始范围应该包括整个长度，才能确保我们想要的结果一定在区间中
	cout<<ans;
	return 0;
 }

ok啦

2.acwing-1227分巧克力

题意理解：

有n块形状为长方形的巧克力，从这些巧克力中切出k块大小相同的正方形来分给k个小朋友。求分成的正方形巧克力在满足数量>=k的条件下，边长的最大值。注意正方形边长是我们的主体，要求最大值，就是要找到最后一个能够满足正方形数<=k条件的边长。由此我们确定是使用第二个模板(即向上取整)。

我们会得到很多满足条件的边长，所以要通过二分来不断缩小区间，来得到边长的最大值，而其决定条件就是，是否该边长在满足分成正方形个数>=k的情况下(check函数的出口)，不断增大(不断试探)，达到一个最大值。

在check函数中，就是要判断每次二分之后得到的边长是否能够满足正方形数<=k条件。边长其实在二分之后已经有一个值了，所以是已知的，而长方形的长和宽已经输入过，且应该存储在两个数组中h[i] w[i] ，这样也是已知的。接下来我们要思考如何计算一个长方形能分成几个边长相同的正方形？由此来判断得出的正方形个数是否满足>=k，那么计算方法就是计算长方形的面积/正方形的面积，得到的商就是个数，对吧？表示出来应该是h[i]* w[i]/mid^2,也就是 (h[i] / x) * (w[i] / x) 这样。

！注意点

所取边长的起始范围应该是1-1e5。从1开始是因为：每个小朋友至少获得一块1*1的巧克力。最大值是1e5是因为巧克力的长和宽最大值是1e5。

另外注意巧克力不能拼接，一个长方形巧克力最多分出正方形之后，如果还有剩余但是剩余的已经不足以再组成一个符合边长的正方形的时候，剩余的部分是舍去的。

视频讲解推荐

下面这个视频是acwing y总的讲解，非常详细，且对模板又讲解了一遍，死循环问题也有讲到，可以看看。

http://www.bilibili.com/video/BV13U4y147rt?vd_source=02dfd57080e8f31bc9c4a323c13dd49c

代码实现

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int h[N], w[N];
bool check(int x)
{
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        count += (h[i] / x) * (w[i] / x);
    }
    return count >= k;
}
int find(int l, int r)
{
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> h[i] >> w[i];
    }
    int ans = find(1, 1e5);
    cout << ans;
    return 0;
}

好啦

3.acwing-730机器人跳跃

其实经过上面两道题的“磨练”，我们很快就能想到解题的思路，应该把能量值作为我们的主体。

题意理解

输入n+1个建筑(注意从下标0开始)，在起始位置上能量为多少的时候，能够满足 “假设机器人在第 k 个建筑，且它现在的能是值是 E，下一步它将跳到第k+1个建筑，如果 H(k+1)> E，那么机器人就失去 H(k+1)-E的能值，否则它将得到 E- H(k+1)的能量值.游戏目标是到达第N个建筑，在这个过程中能量值不能为负数个单位”的条件，且起始能量值越小越好，找到那个能够满足条件的起始能量的最小值。

我们会得到很多满足条件的起始能量，所以要通过二分来不断缩小区间，来得到起始能量的最小值，而其决定条件就是，是否该起始能量在满足到第n个建筑时且整个过程中能量值>0的情况下(check函数的出口)，不断减小(不断试探)，达到一个最小值。由此我们确定使用第一个模板。(即向下取整)

(发现了么？上面这段话在这三道题里话术都是一个模板，我想突出的是题目的思想是相似的)

这是我第一次写的错误代码，这压根就没想清楚啊。。。发什么疯....错误写法

bool check(int x)
{

    for(int i=1;i<=n;i++)
    {
        if(h[i+1]>x)x -= h[i+1]-x;
        else x += x-h[i+1];
    }
    return x>0;
}

！注意点

起始的初始能量范围应该是 0 -1e5 。能量是一个非负数，所以应该从0开始；因为最高的建筑就是1e5，如果第一个建筑的能量是1e5，那么无论如何都可以保证最终完成跳跃，所以我们想要找的最小值，一定在这两个数之间，当然右区间可以更大，只是没必要，也费时间。

如果途中经过了最高的建筑，能量值的更改是 2x-h[k+1]，将会越来越大，1e5不断*2，可能会溢出，所以当我们发现能量值已经超过1e5的时候，就要及时retuen true；因为后续的值一定能是>0的

代码实现

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int h[N], n;

bool check(int x)
{

    for (int i = 1; i <= n; i++)
    {
        x = 2 * x - h[i];
        if (x > 1e5)
            return true;
        if (x < 0)
            return false;
    }
    return true;//因为每经过一个建筑都会判断能量值，所以只要前面过程中没有return，说明一定符合条件
    //return x >= 0;
}
int find(int l, int r)
{
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}
int main()
{
    int E;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i];
    }
    int ans = find(0, 1e5);
    cout << ans;
    return 0;
}

ok啦

感觉这几个题相对前面的直白的告诉你可以用二分的要难一些，我们要思考清楚什么是我们二分的条件，我们是对什么进行二分的。

如果有问题欢迎指出，非常感谢！！

也欢迎交流建议奥。