P8775 [蓝桥杯 2022 省 A] 青蛙过河()

简要题意

有一只青蛙在 \(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)\)。

————————

简要题意

有一只青蛙在 \(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)\)。