[NOIP2015 提高组] 跳石头

zhyyyyy115 / 2023-05-14 / 原文

[NOIP2015 提高组] 跳石头

题目背景

一年一度的“跳石头”比赛又要开始了!

题目描述

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

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

输入格式

第一行包含三个整数 \(L,N,M\)，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 \(L \geq 1\) 且 \(N \geq M \geq 0\)。

接下来 \(N\) 行，每行一个整数，第 \(i\) 行的整数 \(D_i( 0 < D_i < L)\)，表示第 \(i\) 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

一个整数，即最短跳跃距离的最大值。

样例 #1

样例输入 #1

样例输出 #1

提示

输入输出样例 1 说明

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

数据规模与约定

对于 \(20\%\)的数据，\(0 \le M \le N \le 10\)。
对于 \(50\%\) 的数据，\(0 \le M \le N \le 100\)。
对于 \(100\%\)的数据，\(0 \le M \le N \le 50000,1 \le L \le 10^9\)。

题解（二分）

一道非常典型的二分答案的题
首先根据问题它要求输出：最短跳跃距离的最大值。最大值最小值这种问题很容易想到贪心和二分
二分的条件就是：单调+有界。本题的答案也一定在 1 <= ans <= L （有界），另外本题要求最大值，[1, L]答案是一个单调有界的序列，二分确定结果，如果当前值符合结论，则可以缩小二分范围到右边。
最后使用一个judge判断当前的答案是否符合题目要求

如果当前答案符合要求则二分进入到右边
否则二分进入到左边

judge（）：遍历一遍数组，保存上一个元素的值或位置pre。
如果当前的跳跃值小于二分的答案，则将该位置的值删除，继续循环。
如果当前的跳跃值大于等于当前二分的答案，则将更新pre，继续循环。

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define SZ(v) ((int)v.size())
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
using namespace std;
const int N = 1e6+5; 
int _;

int l, n, m;
int a[N];

bool judge(int x) {
   int cnt = 0;
   int pre = 0;
   for(int i = 1; i <= n; i++) {
       if(a[i] - pre < x) {
           cnt++;
       } else {
           pre = a[i];
       }
   }
   if(cnt > m) {
       return false;
   }
   return true;
}

int binary(int l, int r) {
   int ans;
   while(l <= r) {
       int mid = (l + r) / 2;
       if(judge(mid)) {
           ans = mid;
           l = mid + 1;
       } else {
           r = mid - 1;
       }
   }
   return ans;
}

void solve() {
   cin >> l >> n >> m;
   for(int i = 1; i <= n; i++) {
       cin >> a[i];
   }
   a[++n] = l;       // 最大坑点终点也包含在内
   cout << binary(1, l) << "\n";
}

int main() {
   ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); 
   // cin >> _;
   // while(_--) {
       solve();
   // }
   return 0;
}