luogu2678 [NOIp2015]跳石头 (二分答案+贪心)

先二分出一个x，我们要算使最近的跳跃距离>=x的最少移除数量是否<=M就可以了

然后就别dp了...贪心就完事了...我肯定能不移就不移比较好...

 1 #include<bits/stdc++.h>
 2 #define pa pair<int,int>
 3 #define lowb(x) ((x)&(-(x)))
 4 #define REP(i,n0,n) for(i=n0;i<=n;i++)
 5 #define PER(i,n0,n) for(i=n;i>=n0;i--)
 6 #define MAX(a,b) ((a>b)?a:b)
 7 #define MIN(a,b) ((a<b)?a:b)
 8 #define CLR(a,x) memset(a,x,sizeof(a))
 9 #define rei register int
10 using namespace std;
11 typedef long long ll;
12 const int maxn=50050,inf=1e9+1;
13 
14 inline ll rd(){
15     ll x=0;char c=getchar();int neg=1;
16     while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
17     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
18     return x*neg;
19 }
20 
21 int L,N,M,dis[maxn];
22 
23 inline bool judge(int m){
24     int x=0,y=0,i=0;
25     while(y<N){
26         x=y;
27         for(y++;dis[y]-dis[x]<m&&y<N;y++,i++);
28     }
29     return L-dis[x]>=m&&i<=M;
30 }
31 
32 int main(){
33     //freopen(".in","r",stdin);
34     rei i,j,k;
35     L=rd(),N=rd(),M=rd();
36     for(i=1;i<=N;i++) dis[i]=rd();
37     dis[++N]=L;
38     int l=1,r=L,ans;
39     while(l<=r){
40         int m=l+r>>1;
41         if(judge(m)) ans=m,l=m+1;
42         else r=m-1;
43     }
44     printf("%d
",ans);
45     return 0;
46 }