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 (0DiL)D_i\,( 0 D_i L)Di(0DiL) 表示第iii块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出且不会有两个岩石出现在同一个位置。输出格式一个整数即最短跳跃距离的最大值。思路解析枚举二分对最短距离的最大值进行枚举枚举方法采用二分。二分的关键在于出现了单调区间使得枚举的时间复杂度显著降低、本题单调区间提示最大值另一个反面思考直接模拟全过程很复杂可以对移除石头进行计数在比较就可以免除繁琐过程。#includebits/stdc.husingnamespacestd;intd[50010],L,n,m,ans;booljudge(intx){intcnt0,now0;for(inti1;in1;i){if(d[i]-d[now]x)cnt;//别忘了计数elsenowi;//正常跳的情况下就是nowi而不是now}if(cntm)return0;return1;}intmain(){cinLnm;for(inti1;in;i)scanf(%d,d[i]);d[n1]L;intl1,rL;while(lr){intmid(lr)/2;if(judge(mid))ansmid,lmid1;//这里的mid1elsermid-1;//这里的mid-1需要注意}coutans;return0;}对一些错误的思考看见这道题首先考虑到了贪心算法不断删去最小距离值然后不断进行比较。第一次想到了用Class第二次用链表但链表排序难以操作。当再次用类成员进行排序的时候不仅时间复杂度过高还涉及到前后成员的查找。尤其是当距离相同时移除哪一个石头也有相同的判断而且移除之后还涉及到后续移除距离的变化完全无法判断——于是转向二分。
