简要题意
有一只青蛙在 \(1\) 处，有一些石头，位于 \(2,3,4,\cdots n\)，它们的高度是 \(H_2,H_3,\cdots,H_n\)。青蛙每落一次石头，该石头的高度就会 \(-1\)，直至高度为 \(0\)，此时不能落下。如果青蛙的跳跃能力为 \(k\)，那么从 \(i\) 就可以跳到 \([i+1,i+k]\)。求青蛙的最小跳跃能力，使得可以跳 \(2x\) 遍。
思路
首先不难得出结论，如果跳跃能力为 \(k\) 可以胜任，那么对于任意一个长度为 \(k\) 的区间，区间和大于 \(2x\)。
然后大佬们似乎都用了双指针、二分这些我不会的东西，其实我们可以先求一遍前缀和，然后只需要枚举跳跃能力进行验证即可。
时间复杂度 \(O(n^2)\)。（N 方过十万，暴力踩标算）
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,x;
int a[1000005],qzh[1000005];
signed main(){
cin>>n>>x;
n--;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)qzh[i]=qzh[i-1]+a[i];
int nl=1;
for(;;nl++){
bool flag=1;
for(int l=1,r=nl;r<=n;l++,r++){
if(qzh[r]-qzh[l-1]<(x<<1)){
flag=0;
break;
}
}
if(flag){
cout<<nl<<'\n';
return 0;
}
}
}
为什么可以通过
首先，我们加了一个如果区间和小于 \(2x\)，那么就会直接跳出。由于本题 \(H_i\) 最大只有 \(10^4\)，而 \(x\) 最大有 \(10^9\)，\(n\) 只有 \(10^5\)，那么其实 \(H\) 总和最大只有 \(10^9\)，因此随机数据中，绝大多数情况下第一次就跳出了，时间复杂度逼近 \(O(n)\)。
标签：10,int,2x,青蛙,蓝桥,2022,跳跃,P8775 From： https://www.cnblogs.com/zheyuanxie/p/p8775.html