新breath

用户名：15259052877

访问量：3949

签　名：

等　　级
排　　名	7561
经　　验	1302
参赛次数	1
文章发表	6
年　　龄	0
在职情况	学生
学　　校	宁德师范学院
专　　业

　　自我简介：

TA的其他文章

123 二分+数学
浏览：196

最少刷题数二分解法
浏览：623

最大子矩阵(线段树题解）
浏览：616

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （Java代码）

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

　　作者: 新breath　　　　发表时间：2022-10-22 01:35:29 浏览：1664　|　评论：0　

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

~~~
// 该题目题意为 最小的跳跃距离在满足每个过程中的h【k】 ！=0时，k属于【0-n-1】，能过从起点通过 2c次对岸，思路分析：
根据题目意思，很明显想到使用二分查找，因为跳跃距离一定存在一个临界条件使得左边能够到达2c次对岸，右边不能到达2c次对岸，直接判断整个区间在跳跃距离等于x是否能够完全到达对岸很困难，所以想到类似分治的方法，判断在满足x距离的区间下是否能够到达2k次对岸，而为什么选用x作为距离判断是否能够完全到达呢，原因是因为如果x距离到达不了，那么比x更小的距离一定更到达不了对岸，所以贪心的思考问题，枚举x距离的区间只会更到达不了对岸，所以枚举x距离即可，那么为什么一段子区间到达不了2k次对岸就一定不能满足条件呢，原因是因为子区间是整个区间的子集，2k次到达对岸的过程中一定存在一段区间一定要经过这段子区间，该问题反证法易证，而经过的子区间到达不了对岸2k次，那么整段区间一定不行。而能不能到达对岸其实就是h【i】的区间相加能不能到达的问题，区间相加易想到前缀和，而刚开始判断s<2c的原因是因为，如果整段区间到达s减少到0时都到达不了，那么一定到达不了对岸2k次，相当于一个减枝操作//
#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
int n,a[M],c;
typedef long long  ll;
bool check(int x){
	int s=0;
	for(int i=1;i<=min(x,n-1);i++){
		s+=a[i];
	}
	if(s<c){
		return 0;
	}
	for(int i=x+1;i<=n-1;i++){
		s-=a[i-x];
		s+=a[i];
		if(s<c){
			return 0;
		}
	}
	return 1;
	
}
int main(){
	scanf("%d%d",&n,&c);
	c*=2;
	for(int i=1;i<=n-1;i++){
		cin>>a[i];
	}
	int l=0,r=n;
	while(l+1!=r){
		int m=(l+r)>>1;
		if(check(m)){
			r=m;
		}else{
			l=m;
		}
	}
	cout<<r<<endl;
	return 0;
}
~~~

0.0分

15 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

新breath

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （Java代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

Hello, world! （Java代码）

宏定义（C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （Java代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

简单的a+b （C语言代码）