洛谷P2678 [NOIP2015 提高组] 跳石头 题解

题目链接：P2678 [NOIP2015 提高组] 跳石头

题意：

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

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

对于 \(100\%\)的数据,\(0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000\)。

求最小值最大，二分经典题。

为什么是二分呢？因为我们并不知道最小值是多少

我们可以枚举一个最小值，然后使它尽可能的大

对于有单调性的题目可以使用二分，显然这题有单调性

然后就没啥了，二分一下就好了

注意终点不是 \(N\) 。时间复杂度 \(O(N \log L)\)

相信大家做这题的时候应该二分不太熟，

这里给一个二分的板子（我是在《算法竞赛进阶指南》上学到的）

---

• 求枚举值的最小值，则符合条件就使r=mid，

  表示答案在 \([l,\text{mid}]\) 间，注意这里 \(\text{mid}\) 是可行的。

  例如：在单调递增序列 \(a\) 中查找 \(\ge x\) 的数中最小的一个 （ \(x\) 或 \(x\) 的后继）

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

• 求枚举值的最大值，则符合条件就使l=mid，

  表示答案在 \([\text{mid},r]\) 间，注意这里 \(\text{mid}\) 是可行的。

  例如：在单调递增序列 \(a\) 中查找 \(\le x\) 的数中最大的一个（ \(x\) 或 \(x\) 的前驱）

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

---

题目代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e5+15)

int n,m,d,a[N],l,r,mid;
int ck(int x)
{
    int tot=0,i=0,now=0;
    while(i++ <= n)
    {
        if(a[i]-a[now]<x) ++tot;
        else now=i;
    }
    return tot<=m; 
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> d >> n >> m;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    a[n+1]=d;
    l=1;r=d;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(ck(mid))l=mid;
        else r=mid-1;
    }
    cout << l << '\n';
    return 0;
}