跳石头

链接

题目给出终点L(最大数),和距起点1~L的各石头(数字),要求我们拿走M个石头(数字),使各石头间的距离最小值最大

例如给出一段序列 0 1 11 22 26 31 37 47(0代表起点,47代表终点),拿走三块石头,使各石头间的距离最小值最大

我们可以拿走 1 26 31,得出的结果为10

这题我们可以采用二分法+贪心的思想

最终结果肯定介于[ 1 , L ] ,我们先假设这个最大值为(1+L)/2,如果偏小,那么结果就介于

[ ( 1 + L ) / 2 , L ],依次不断对区间缩小,直到左区间超过右区间

怎么判定偏大偏小呢,我们不妨思考,如果p成立,那么p-1肯定成立,最大值肯定大于最大值减一

而p+1缺不一定成立(p可能就是最大值)

如果某个石头与上一个石头的距离太小,我们就要移除该石头,直到距离足够

如果,距离已经足够,我们就把索引移到该石头,判定该石头之后的石头与其的距离是否合适

想法有了,代码实现如下

#include<iostream>
#include<vector>
using namespace std;
int main() {
	int L, M, N;
	cin >> L >> N >> M;
	vector<int>stones(N + 2);
	stones[0] = 0;
	stones[N + 1] = L;
	for (int i = 1;i <= N;i++) {
		cin >> stones[i];
	}
	int left = 1, right = L;
	int ans = 0;
	while (left <= right) {
		int maxdis = (left + right) / 2;
		int lastpos = 0;
		int removecount = 0;
		for (int i = 1;i <= N + 1;i++) {
			if (stones[i] - lastpos < maxdis) {
				removecount++;
				if (removecount > M) break;
			}
			else {
				lastpos = stones[i];
			}
		}
		if (removecount <= M) {
			ans = maxdis;//答案暂时定为maxdis,接着判定超过maxdis的是否成立
			left = maxdis + 1;
		}
		else {
			right = maxdis - 1;
		}
	}
	cout << ans;
}

时间复杂度:O(N log L)

空间复杂度:O(N)