POJ 3258 River Hopscotch 二分

题意：奶牛们喜欢在河里的石头上玩跳房子游戏，每次从一个石头跳到另一个石头上。现在知道起点的石头，终点的石头，以及终点石头到起点石头的距离L。又知道起点-终点之间还有N个石头，每个石头到起点的距离记为rock[i]。Farmer John想去掉N个石头中的M个，问如何去掉使得任意两块石头之间的距离的最小值最大。

#include
#include
using namespace std;int L, N, M;
int rock[200000];bool check ( int len )
{int i, j, cnt = 0;for ( i = 1; i <= N + 1; i++ ){j = i - 1;while ( i <= N + 1 && rock[i] - rock[j] < len ){i++; cnt++;}if ( cnt > M ) return false;}return true;
}int bfind ( int left, int right )
{while ( left + 1 < right ) //放防止出现left = mid的死循环{int mid = (left+right)/2;if ( check(mid) ) left = mid; //始终保持一边的合法性。else right = mid - 1;}if ( check(right) ) return right; //选择最优值，因为right>=left，若right合法，则它更优else return left;
}int main()
{scanf("%d%d%d",&L,&N,&M);for ( int i = 1; i <= N; i++ )scanf("%d",&rock[i]);rock[0] = 0; rock[N+1] = L;sort(rock,rock+N+2);int ret = bfind ( 0, L );printf("%d\n",ret);return 0;
}

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