P2678 跳石头（二分算法）

P2678 [NOIP 2015 提高组] 跳石头

题目描述

组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有NNN块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

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

输入格式

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

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

输出格式

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

思路解析

枚举+二分
对最短距离的最大值进行枚举，枚举方法采用二分。
二分的关键在于出现了单调区间，使得枚举的时间复杂度显著降低、
本题单调区间提示：最大值
另一个反面思考：直接模拟全过程很复杂，可以对移除石头进行计数在比较，就可以免除繁琐过程。

#include"bits/stdc++.h"usingnamespacestd;intd[50010],L,n,m,ans;booljudge(intx){intcnt=0,now=0;for(inti=1;i<=n+1;i++){if(d[i]-d[now]<x)cnt++;//别忘了计数elsenow=i;//正常跳的情况下就是now=i，而不是now++；}if(cnt>m)return0;return1;}intmain(){cin>>L>>n>>m;for(inti=1;i<=n;i++)scanf("%d",&d[i]);d[n+1]=L;intl=1,r=L;while(l<=r){intmid=(l+r)/2;if(judge(mid))ans=mid,l=mid+1;//这里的mid+1elser=mid-1;//这里的mid-1需要注意}cout<<ans;return0;}

对一些错误的思考
看见这道题首先考虑到了贪心算法，不断删去最小距离值然后不断进行比较。
第一次想到了用Class，第二次用链表，但链表排序难以操作。
当再次用类成员进行排序的时候，不仅时间复杂度过高，还涉及到前后成员的查找。尤其是当距离相同时，移除哪一个石头也有相同的判断，而且移除之后还涉及到后续移除距离的变化，完全无法判断
——于是转向二分。