本文主要是介绍POJ 3258 River Hopscotch 二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：奶牛们喜欢在河里的石头上玩跳房子游戏，每次从一个石头跳到另一个石头上。现在知道起点的石头，终点的石头，以及终点石头到起点石头的距离L。又知道起点-终点之间还有N个石头，每个石头到起点的距离记为rock[i]。Farmer John想去掉N个石头中的M个，问如何去掉使得任意两块石头之间的距离的最小值最大。
#include<cstdio>
#include<algorithm>
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;
}
这篇关于POJ 3258 River Hopscotch 二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
