这道题用来巩固二分查找算法，（我二分太渣了）

 

题目描述

一年一度的“跳石头”比赛又要开始了!
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有N块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走M块岩石(不能移走起点和终点的岩石)。

 

输入

第一行包含三个整数L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。
接下来N行,每行一个整数,第i行的整数Di(0<Di<L)表示第i块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。

 

输出

只包含一个整数,即最短跳跃距离的最大值。

 

样例输入

复制样例数据

25 5 2
2
11
14
17 
21

样例输出

4

 

提示

 

将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4(从与起点距离 17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。

 

题解思路：

第一步：看到题目要求，求最短跳远距离的最大值，让你输出最短跳跃距离，刚拿这道题瞬间懵逼，什么意思？最短距离的最大值？意思就是说，跳跃过程中，这个距离是最短距离，为什么会出来一个最大值呢？因为可以出现多个最短距离(题目中可以移走石头,就有可能使得最短距离变大)。

第二步：既然我们知道了最短距离，我们挨个枚举就可以了，我们假定一个长度L是最短距离，我们判断一下这个距离可不可以是最短距离。怎么判断，我们把每一次跳跃都模拟一下，例如：

（1）:从1号跳到2号，如果1号2号的距离之差为d并且d>L，就说明可以满足，然后我们跳到2号.

（2)：从2号跳到3号，如果2号3号之间的距离为d并且d<L，那么此时不满足条件，因为我们假设了L是当前的最短距离，这期间出现比L短的绝对不可以，此时我们就把这一块移走。

（3)：移走之后 从2号要跳到4号，这是的d>L，我们就可以跳过去了。

（4)：其实我们这里如果不加移走石头的限制，最短跳跃距离的最大值就是第一块石头与终点的距离，因为直接移走全部石头就可以了，但是题目中给出了一个k，这个k就是移走石头的限制，给了这个限制之后我们就可以进行判定了。

  (5)：假设我们已经跳到了终点，经过上述模拟，绝对确保我们假设的这个距离L是最短距离，但是由于k次移动的限制我们需要判断一下，移动了多少次，如果移动的次数超出了现在的允许次数，那么绝对是不可以的。如果不理解：我们可以这么想，如果少移动一次，那么绝对会有一个距离比现在L小，因为我们是根据有一段距离比L小才移动石头的使得这段距离大于L(上述步骤2)。

第三步：模拟完了之后，我们思路也就出来了，枚举从1-最大距离的任何一个距离，把该距离作为最小距离，我们判定一下可不可以，也就是超不超的出k的限制，用一个ans记录一下就可以了:

ans=-INF;
if(judge(x))//把x作为最短距离看是否可以
    ans=max(ans,x)

第四步：前面的枚举做法完全可以，但是T掉了，很明显判断当前距离可不可行这个函数我们有一个复杂度，就是从1遍历到n，然后我们在挨个枚举最短距离，假设最大距离是m，时间复杂度：O(m*n)。题目中m最大为1000000000 n为1000000(不超时不可能叭)

第五步：我们优化一下这个枚举，这个方法就是这个题目要考察的内容啦，二分查找。

我来简单概括一下二分查找：

首先，二分查找适用于找最大值的最小值，或者是最小值的最大值。比如说查找从大到小排好序的一段序列(a[n])中，第一个比m大的数，我们可以首先枚举中间那个数，在这里我们令中间那个数为a[mid]。如果a[mid]比m小，说明我们要找的数不在mid左边，而在mid的右边，因为序列已经从小到大排序了，既然a[mid]比m小，a[mid]之前绝对比m小，所以我们把区间 转移到了[mid+1,n]之间。还有一种情况：如果a[mid]比现在要找的数大，说明他是一个可行解，也就是他满足比m大，但是不一定是第一个比他大的，我们就看看他左边有没有比m大的，因为从小到大排序嘛。所以这样一步步的判断，这个区间会一步步缩小，直至缩小到满足题意的那个点，并且我们也发现如果要进行二分查找原序列必须有序！

这样就完成了找到第一个数,我写一下这个模板:

int a[maxn];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);//我们假定输入的顺序就是从小到大，因为我们可以自己输呀，而且只是个模板而已，但是实际情况必须要排序哦！！！
    int l=1,r=n;//定义起始位置和终止位置
    int ans,loca;//一个记录数，一个记录位置
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(a[mid]>=k)
        {
            ans=a[mid];
            r=mid-1;
            loca=mid;
        }
        else
            l=mid+1;
    }
    printf("%d is in the %d of the sequence",ans,loca);
    return 0;
}

这个模板是二分查找一段序列中，数字k出现的第一个位置在哪，当然(敲黑板！！)最好不要套模板，要自己理解一下，原理没有那么难懂。

在写一个查找比k大的第一个数的模板：

int a[maxn];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);//我们假定输入的顺序就是从小到大，因为我们可以自己输呀，而且只是个模板而已，但是实际情况必须要排序哦！！！
    int l=1,r=n;//定义起始位置和终止位置
    int ans,loca;//一个记录数，一个记录位置
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(a[mid]>k)
        {
            ans=a[mid];
            r=mid-1;
            loca=mid;
        }
        else
            l=mid+1;
    }
    printf("%d is in the %d of the sequence",ans,loca);
    return 0;
}

其实就是把大于等于号改成大于号就可以了，仔细想想为什么。

这两种查找对我们有很大实际意义，我们可以计算出一个数字k连续出现的长度，比如说我们用第一个模板可以找出大于等于k的第一个数，其实就是k第一次出现的位置记为loca1，再用第二个模板找出大于k的第一个数，位置记为loca2，所以说k的最后一次出现的位置就是loca2-1，所以距离就是loca2-1-loca1+1，其实就是loca2-loca1。更多实际应用，自己慢慢去发掘叭。

咳咳，扯多了，回归原题。

第六步：我们按照二分的思想直接二分可能出现的最短距离就可以了，如果这个距离可以，也就是没有超过k次的限制，我们就把区间右移，找一个更大的作为最短距离，因为题目说要找出最大的最短距离呀。如果不可以，说明我们枚举的这个距离太大了(因为移动次数越多，说明这个 最短距离 越大，因为移动好几个石头才可以满足要求)，所以我们就区间左移，再找一个小的最短距离，这样如此往复，最后的距离即为最短距离的最大值！

第七步：当然是看题目，注意范围，L:1000000000,所以long long 要安排一下叭？然后用一个ans记录一下当前的最短距离，这道题就结束啦，总而言之，这道题就是卡的二分，暴力枚举是过不了的，也多亏这道题，可以让我总结一下二分的思想巩固基础础，好了，扯的也够多了。

代码+注释附上：

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const ll INF=1e9;
/*坚持不懈，无懈可击*/
/*中国有句古话，叫做置之死地而后生！*/
ll  n,m,k;
ll a[maxn];
bool judge(ll x)
{
    int now=0;
    int tot=0;
    for(int i=1;i<=n+1;i++)
    {
        if(a[i]-a[now]>=x)//如果比这个最短距离大，我们跳过去
            now=i;
        else
            tot++;//否则，我们要把这个石头移走，跳下一个
    }
    if(tot>k) return false;
    else return true;
}
int main()
{
    scanf("%lld%lld%lld",&m,&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    a[n+1]=m;//一定不要忘记终点！
    ll l=1,r=m;
    ll ans;
    while(l<=r)//开始二分查找
    {
        ll mid=(l+r)/2;
        if(judge(mid))
        {
            ans=mid;//记录当前的可行解，而不一定是最优解，最优解会在之后更新。
            l=mid+1;//我们去他的右区间看看，还有没有比他大的数满足条件
        }
        else
            r=mid-1;//不符合我们只好去找一个小的距离
    }
    printf("%lld\n",ans);//最后这个ans一定是最优解
    return 0;
}

祝大家一次AC！