【POJ3258】River Hopscotch 二分答案，贪心check

题意：第一行knm，有n+2个石头在数轴上（k是第n+2个石头离第一个的距离），要删掉m个，使两两间距的最小值最大，并求这个值。

题解：排序一下，然后扫一遍贪心决定删哪些。

#include 
#include 
#include 
#define N 50500
#define inf 0x3f3f3f3f
using namespace std;
int dist[N],n,m;
int main()
{
//	freopen("test.in","r",stdin);int i,j,k;scanf("%d%d%d",&k,&n,&m);dist[++n]=k;for(i=1;i<=n;i++)scanf("%d",&dist[i]);int l=1,r=inf,mid,ans=1,num;sort(dist+1,dist+n+1);for(i=1;i<=40;i++){mid=l+r>>1;num=0;int now=0;for(j=1;j<=n;j++){if(dist[j]-dist[now]>=mid){now=j;}else num++;}
//		printf("%d : %d\n",mid,num);if(num<=m)l=mid+1,ans=mid;else r=mid;}printf("%d\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！