蓝桥-13届-青蛙过河

看完没什么思路

就类似于看完一个自然语言描述的问题后，没法把它转换编程模型

题目的意思是y至少要多大，才能足够青蛙跳2x次

因为跳跃过程是可逆的，于是能否往返跳2x次等价于同向跳2x次

由于当y=n时，青蛙不需要踩任何石头直接跳过去，于是y一定是小于等于n的一个数
照这个数我们可以使用二分法提高效率

同时对于每一次，判定的条件究竟是什么？足够跳2x次就变成了：任意y范围内的石头高度总和都>=2x

这哪儿想得到，已经不属于编程问题了

#include <iostream>
#include <vector>
using namespace std;


int n, x;
vector<int> preSum;
bool check(int y) {
	// 检查所有长度为y的区间
	for (int i = 1; i < n - y; i++) {
		int right = i + y - 1;
		if (preSum[right] - preSum[i - 1] < 2 * x) return false;
	}
	return true;
}

int main() {

	cin >> n >> x;
	preSum.resize(n);

	// 利用前缀和提高效率
	for (int i = 1; i <= n; i++) {
		cin >> preSum[i];
		preSum[i] += preSum[i - 1];
	}

	int left = 1, right = n, ans = -1;
	while (left < right) {
		int mid = (left + right) / 2;
		if (check(mid)) ans = mid, right = mid - 1;
		else left = mid + 1;
	}
	cout << ans;
	return 0;
}