题意:给一组数据分别是一组石头距离河岸的距离,求移走固定数目的石头之后,使得剩余石头之间的最小距离最大。
做法:二分。二分结果(最小距离),如果达到这个距离了所移走的石头数目比给定的数目多则缩小最小距离,如果移走的石头数目比给定的数目少则增大距离。最后得到答案。。。【做了太久了忘记wa了好多次最后怎么改的了。。。。【ps。。第一个二分题。。。看了一下别人的题解。。。我真垃圾::>_<::】
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int dis[50005]; int L,N,M; bool ok(int mid) { int ans=0,sum=0; for(int i=1;i<=N+1;i++) { sum+=dis[i]-dis[i-1]; if(sum<=mid) ans++; else sum=0; } return ans<=M; } int main() { scanf("%d%d%d",&L,&N,&M); memset(dis,0,sizeof(dis)); for(int i=1;i<=N;i++) { scanf("%d",&dis[i]); } dis[N+1]=L; sort(dis+1,dis+N+1); int l=1,r=L,mid; while(l<=r) { mid=(l+r)>>1; if(ok(mid)) l=mid+1; else r=mid-1; } printf("%d\n",l); }