【NOIP2015】 跳石头

CJOJ——P2566 - 【NOIP2015】 跳石头

题面:

??这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)

解法:

最小的最大,采用二分做法:
??二分答案 mid,然后选取一个石头,在这个石头后面凡有距离小于 mid 的全部移走,
??然后跳到距离$≥mid$的第一个石头上,继续以上操作
??如果移走的石头数不大于 m,则符合条件

复杂度:

O($nlogL$)

代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=50010;
int t[MAXN];
int L,n,m;
bool check(int lim)
{int cnt=0;for(int i=0,x=0;i<=n;){i++;if( t[i]-t[x]<lim )   cnt++;else   x=i;}if( cnt>m )   return false ;else   return true ;
}
int main()
{scanf("%d%d%d",&L,&n,&m);for(int i=1;i<=n;i++)   scanf("%d",&t[i]);t[n+1]=L;int l=0,r=L;while( l<=r ){int mid=(l+r)/2;if( check( mid ) )   l=mid+1;else   r=mid-1;}printf("%d\n",l-1);return 0;
}