AcWing
4647. 青蛙过河(第十三届蓝桥杯省赛C++ A组/C组)
首先考虑答案所具有的性质，问题答案的范围在1~n，当步长为0，一定不能过河，所以答案至少是1；当步长为n，一步就能过河，那么一定可以过河。
假如恰好过河的步长是res，那么对于任意的步长i，如果i<res，那么一定不能过河；如果i>=res，那么一定可以过河，所以问题的答案具有二段性，使用二分搜索答案。
现在考虑二分的check()函数。往返x次，等价于从家到学校2x次。假设现在的步长为len，考虑到学校的距离为len的区间[n-len+1, n]，需要满足sum_h[n-len+1, n] >= 2x，才能保证完成最后一跳；类似地，区间[n-len, n-1]也需要满足sum_h[n-len, n-1] >= 2x，保证其可以传递到上一个区间的状态。所以，对于check()函数，可以判断[1, n-1]范围内所有长度为len的子区间和是否都>=2x。如果暴力加和，可能会超时，对区间加和的操作可以通过前缀和实现，维护前缀和数组pre[N]，这样遍历区间[1, n-1]的时间复杂度是$O(n)$，加上二分的时间复杂度$O(logn)$，总的时间复杂度是$O(nlogn)$.
#include <bits/stdc++.h>
using namespace std;
int n, x;
const int N = 100010;
int pre[N];
bool check(int len){
for(int i = len; i <= n - 1; i++){
int sum = pre[i] - pre[i - len];
if(sum < 2 * x) return false;
}
return true;
}
int main(){
cin >> n >> x;
for(int i = 1; i <= n; i++) cin >> pre[i], pre[i] += pre[i - 1];
int l = 1, r = n;
while(l < r){
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << r << endl;
return 0;
}