蓝桥杯2022年第十三届省赛真题-青蛙过河

解题思路:

来x去x次，等价于来2*x次（即去的x次每次反向走，变成来的x次）。

一个青蛙跳2*x次，等价于2*x个青蛙同时跳一次。

贪心算法，一次跳跃尽可能跳最远的那个石头。
二分法，设跳跃能力y，每一段连续长度y内石头总数都要超过2*x，才能过河；若有一个区间y内石头总数小于2*x，该区间前一个区间的2*x个青蛙就无法全部通过这个区间。

注意事项:
数组类型,sum可能会超过int，故用long long
参考代码:

#include <iostream>
#include <cstdio>
#include <cstring>//strlen、strcmp 
#include <cmath>
#include <cstdlib>//malloc
#include <algorithm>
using namespace std;

#define maxn 100010
int n,x;//n-1个石头，2*x次通过 
int h[maxn];
long long sum[maxn];//每块石头高度、高度的前缀和数组 
int y;//弹跳能力 
bool above(int a){//每段区间长度为a时,判断其内总石头数是否>=2*x
//注意是任意一段连续的长度为a的区间都要满足才为真,并不是分块 
	for(int i = 1;i <= n-a;++i){
		int r = i+a-1;
		if(sum[r]-sum[i-1]<2*x){
			return false;
		}
	}
	return true;
}
int main() {
	scanf("%d%d",&n,&x);
	for(int i = 1;i < n;++i){
		scanf("%d",&h[i]);
		sum[i] = sum[i-1] + (long long)h[i];
	}
	y = n;
	int l=1,r=n,mid;
	while(l < r){//二分法，类似lower_bound 
		mid=l+(r-l)/2;
		if(above(mid)){//若弹跳能力为mid时可以,则y最多为mid,查找左区间 
			r = mid; 
		}else{//若mid时不行，则y必大于mid,查找右区间 
			l = mid+1;
		}
	}//最后退出为l==r 
	y = l;
	printf("%d\n",y); 
	
		
	return 0;
}