POJ 3258 River Hopscotch 题解 《挑战程序设计竞赛》

POJ 3258 River Hopscotch

奶牛跳房子：从N块石头中移除M块，使得间距最小值最大。

3.1不光是查找值！“二分搜索”

最大化最小值

再听会儿金融课我就要变蠢了

终于刷到中级篇了，这题是POJ2456的变形，可以想象成从N块石头里挑出N-M块，使得最小间距最大。在实现上，需要贪心地选取比间距d稍微大那么一点（尽量小）的作为编号小的石头，所以需要排个序再去搜索。

举个例子：

0 2 11 14 17 21 25 
5
---------13
3
7
不满足
---------6
2
4
6
7
不满足
---------3
2
3
4
5
满足
---------4
2
4
5
6
满足
---------5
2
4
6
7
不满足
所以答案是4

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_N 50000 + 16
int L, N, M;
int D[MAX_N];


//************************************
// Method:    C
// FullName:  C
// Access:    public 
// Returns:   bool
// Qualifier: 是否可能使得所有石头之间的距离不小于d
// Parameter: int d
//************************************
bool C(int d)
{
	int last = 0;
	for (int i = 1; i < N - M; ++i)
	{
		int current = last + 1;
		while (current < N && D[current] - D[last] < d)	// 搜寻满足条件的最小位置
		{
			++current;
		}
		if (current == N)	// 都不满足条件
		{
			return false;
		}
		last = current;		// 继续搜寻下一个满足条件的最小位置，放置下一个空位
	}
	return true;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin >> L >> N >> M;
	for (int i = 1; i <= N; ++i)
	{
		cin >> D[i];
	}
	++N;	// 0号是起始点，所以加一
	D[N] = L;
	++N;	// N号是结束点，还要加一
	sort(D, D + N);
	int lb = 0, ub = L + 1;
	while (ub - lb > 1)
	{
		int mid = (lb + ub) / 2;
		if (C(mid))
		{
			lb = mid;
		}
		else
		{
			ub = mid;
		}
	}
	cout << lb << endl;

#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3258 River Hopscotch 题解 《挑战程序设计竞赛》