首页 > 代码库 > POJ3528移石头

POJ3528移石头

2024-07-13 00:01:26   223人阅读

题目大意：

河道两旁直线上有两块石头不能移动，距离为L，但中间放置了N块石头并列出这N块石头到起点的距离，可以移走M块，那么移走石头后每次牛跨石头的最小距离如何达到最大值，输出这个最大值

 

让最小距离的最大值就直接想到二分法，之前也用循环通过一次次移走石头但移走的石头数量一大就会超时。

 

代码如下：

 1 #include<stdio.h> 2 #include<algorithm> 3 #include<stdlib.h> 4 using namespace std; 5  6 const int MAXN = 50005; 7 int L,N,M; 8 int ds[MAXN];//每块石头距离起点的距离 9 10 //判断在达到最小跨越距离为m的情况下移动的石头数目是否小于给定的M,为之后所能达到的最大值做铺垫;11 bool judge(int m){12     int start=0,last=1,cnt=0;13     while(last<=N+1){14         if(ds[last]-ds[start]<m) cnt++;15         else start=last;16         last++;17     }18     if(cnt<=M) return true;19     else return false;20 }21 22 int main()23 {24     scanf("%d%d%d",&L,&N,&M);25     ds[0]=0;26     for(int i=1;i<=N;i++){27         scanf("%d",&ds[i]);28     }29     ds[N+1]=L;30 31     sort(ds+1,ds+N+1);32 33     //进行二分搜索来确定那个距离的最大值;34     int start=0,last=L,mid,result=0;35     while(start<=last){36         mid=(start+last)/2;37         if(judge(mid)) {38             start = mid+1;39             result=mid;40         }41         else last=mid-1;42     }43     printf("%d\n",result);44 45     return 0;46 }


联系
我们