第一遍
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 int d,n,m; 6 int p[50001]; 7 bool check(int a){ 8 int tot=0; 9 int f=0; 10 for(int i=0;i<n;i++) 11 if(p[i]-f<a) tot++; 12 else f=p[i]; 13 14 if(tot<=m) return 1; 15 else return 0; 16 } 17 int main(){ 18 scanf("%d%d%d",&d,&n,&m); 19 int l=1,r=d,mid,ans; 20 for(int i=0;i<n;i++) 21 scanf("%d",&p[i]); 22 23 while(l<=r){ 24 mid=(r+l)>>1; 25 if(check(mid)){ 26 ans=mid; 27 28 //cout<<mid<<endl; 29 l=mid+1; 30 } 31 else r=mid-1; 32 33 } 34 cout<<ans; 35 }通过了洛谷评测， 没通过UOJ的extra test
后来发现还得把对岸存上，a[ n +1 ] = L；
#include <iostream> #include <cstdio> using namespace std; #define re register int L, n, m; int d[ 50010 ]; inline int judge( int mid ){ int upone = 0; int havedone = m; for(re int i = 1; i <= n + 1; i++){ if( d[ i ] - upone < mid){ havedone--; } else upone = d[ i ]; } if(havedone < 0) return 0; else return 1; } int main(){ scanf("%d%d%d", &L, &n, &m); for(re int i = 1;i <= n; i++) scanf("%d", &d[ i ]); d[ n+1 ] = L; int l = 1; int r = L; int mid; int ans = 0; while( l <= r){ mid = (l + r) >> 1; if(judge(mid)){ ans = mid; l = mid + 1; } else r = mid - 1; } cout<<ans; return 0; }即可通过
转载于:https://www.cnblogs.com/grejioh/p/7764300.html
相关资源：JAVA上百实例源码以及开源项目