洛谷P2678 [NOIP 2015 提高组] 跳石头

P2678 [NOIP 2015 提高组] 跳石头题目背景NOIP2015 Day2T1题目描述一年一度的“跳石头”比赛又要开始了这项比赛将在一条笔直的河道中进行河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间有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​(0Di​L) 表示第iii块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出且不会有两个岩石出现在同一个位置。输出格式一个整数即最短跳跃距离的最大值。输入输出样例 #1输入 #125 5 2 2 11 14 17 21输出 #14说明/提示输入输出样例 1 说明将与起点距离为222和141414的两个岩石移走后最短的跳跃距离为444从与起点距离171717的岩石跳到距离212121的岩石或者从距离212121的岩石跳到终点。数据规模与约定对于20%20\%20%的数据0≤M≤N≤100 \le M \le N \le 100≤M≤N≤10。对于50%50\%50%的数据0≤M≤N≤1000 \le M \le N \le 1000≤M≤N≤100。对于100%100\%100%的数据0≤M≤N≤50000,1≤L≤1090 \le M \le N \le 50000,1 \le L \le 10^90≤M≤N≤50000,1≤L≤109。//lg2678-1#includecstdio#definemaxn50010usingnamespacestd;intL,n,m,ans;inta[maxn];boolP(intd){intcur,removed0,last0;for(inti1;in1;i){if(in){cura[i];}elsecurL;if(cur-lastd){removed;}else{lastcur;}}returnremovedm;}intmain(){scanf(%d%d%d,L,n,m);for(inti1;in;i)scanf(%d,a[i]);intl0,rL;while(lr){intmidl(r-l)/2;if(P(mid)){ansmid;lmid1;}elsermid-1;}printf(%d\n,ans);return0;}