路标设置
此题和跳石头很相似，都是二分答案，模拟判断是否可行
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 #define N 100010 5 int L,n,k,x[N]; 6 inline int read(){ 7 int x=0; char c=getchar(); 8 while(c<'0'||c>'9') c=getchar(); 9 while('0'<=c&&c<='9') { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); } 10 return x; 11 } 12 bool ok(int t){ //判断是否可行 13 int sum=0; 14 for(int i=1;i<max(n,2);i++) 15 sum+=(x[i+1]-x[i]-1)/t; 16 return sum<=k; 17 } 18 int main() 19 { 20 scanf("%d%d%d",&L,&n,&k); 21 for(int i=1;i<=n;i++) 22 x[i]=read(); 23 int l=1,r=L; 24 while(l<r){ //二分答案 25 int mid=(l+r)>>1; 26 if(ok(mid)) r=mid; 27 else l=mid+1; 28 } 29 printf("%d\n",l); 30 return 0; 31 }