看完没什么思路
就类似于看完一个自然语言描述的问题后，没法把它转换编程模型
题目的意思是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;
}