csp信奥赛C++高频考点专项训练：【二分答案】案例4：跳石头-酒店常州论坛

csp信奥赛C++高频考点专项训练：【二分答案】案例4：跳石头

题目描述

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

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

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

输入格式

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

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

输出格式

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

输入输出样例 1

输入 1

25 5 2 2 11 14 17 21

输出 1

说明/提示

输入输出样例 1 说明

将与起点距离为2 22和14 1414的两个岩石移走后，最短的跳跃距离为4 44（从与起点距离17 1717的岩石跳到距离21 2121的岩石，或者从距离21 2121的岩石跳到终点）。

数据规模与约定

对于20 % 20\%20%的数据，0 ≤ M ≤ N ≤ 10 0 \le M \le N \le 100≤M≤N≤10。
对于50 % 50\%50%的数据，0 ≤ M ≤ N ≤ 100 0 \le M \le N \le 1000≤M≤N≤100。
对于100 % 100\%100%的数据，0 ≤ M ≤ N ≤ 50000 , 1 ≤ L ≤ 10 9 0 \le M \le N \le 50000,1 \le L \le 10^90≤M≤N≤50000,1≤L≤109。

AC代码

#include<bits/stdc++.h>usingnamespacestd;intL,N,M,a[50010],ans;// 检查函数，判断是否可以在移除不超过M块岩石的情况下，使所有跳跃距离至少为xboolcheck(intx){intlast=0;// 上一个未被移除的岩石位置，初始为起点0intcnt=0;// 统计需要移除的岩石数量for(inti=1;i<=N;i++){if(a[i]-last<x){// 当前岩石与上一个未被移除的岩石距离不足x，需移除当前岩石cnt++;}else{// 距离足够，保留当前岩石，更新lastlast=a[i];}}// 检查最后一个未被移除的岩石到终点的距离if(L-last<x)cnt++;// 若不足x，需移除最后一个岩石，但终点不可移除，故cnt增加returncnt<=M;// 判断总移除数是否在允许范围内}intmain(){cin>>L>>N>>M;for(inti=1;i<=N;i++)cin>>a[i];intl=1,r=L;// 二分范围：最短距离可能的最大值范围[1, L]while(l<=r){intmid=(l+r)/2;if(check(mid)){// 当前mid可行，尝试寻找更大的值ans=mid;l=mid+1;}else{// 当前mid不可行，减小范围r=mid-1;}}cout<<ans;return0;}

功能分析

问题目标：在最多移除M块岩石的情况下，最大化选手跳跃过程中的最短距离。
二分答案：通过二分法确定可能的最大最短距离x。对于每个x，使用check函数验证是否可行。
check函数逻辑：
- 遍历每块岩石，若当前岩石与上一个保留岩石的距离小于x，则移除当前岩石。
- 遍历结束后，检查最后保留的岩石到终点的距离是否小于x，若是则需移除该岩石。
- 统计总移除数是否不超过M，若成立则x可行。
二分边界：初始范围为1到L，确保覆盖所有可能值。最终答案通过调整左右边界确定。

完整信奥赛C++普及组CSP-J一等奖通关刷题题单及题解，请关注专栏：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

企业官网建设流程全解析