bzoj1650[Usaco2006 Dec]River Hopscotch 跳石子*

bzoj1650[Usaco2006 Dec]River Hopscotch 跳石子

题意：

数轴上有n个石子，第i个石头的坐标为Di，现在要从0跳到L，每次跳都从一个石子跳到相邻的下一个石子。现在问移走这M个石子后，相邻两个石子及0到最前一个石子及最后一个石子到L距离的最小值的最大值是多少。n≤50000

题解：

为什么有NOIP2015即视感~二分距离最小值，然后如果当前石子和上一个石子相差小于二分值就将这个石子移走，如果位置L与上一个石子相差小于二分值，此时若还没有移满M个且有没移走的石子，就可以将其移走，否则不合法。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define inc(i,j,k) for(int i=j;i<=k;i++)
 5 #define maxn 50100
 6 using namespace std;
 7 
 8 inline int read(){
 9     char ch=getchar(); int f=1,x=0;
10     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
11     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
12     return f*x;
13 }
14 int n,m,d,rc[maxn],l,r,ans;
15 bool check(int x){
16     int y=0,z=0;
17     inc(i,1,n){if(rc[i]-y<x){z++; if(z>m)return 0;}else y=rc[i];}
18     if(d-y<x&&(z==m||z==n))return 0; return 1;
19 }
20 int main(){
21     d=read(); n=read(); m=read(); inc(i,1,n)rc[i]=read(); sort(rc+1,rc+n+1); l=1; r=1000000000;
22     while(l<=r){
23         int mid=(l+r)>>1; if(check(mid))ans=mid,l=mid+1;else r=mid-1;
24     }
25     printf("%d",ans); return 0;
26 }

20160730