[蓝桥杯 2022 省 A] 青蛙过河
题目描述
小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。
河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降
1
1
1，当石头的高度下降到
0
0
0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到
0
0
0 是允许的)。
小青蛙一共需要去学校上
x
x
x 天课，所以它需要往返
2
x
2x
2x 次。当小青蛙具有一个跳跃能力
y
y
y 时，它能跳不超过
y
y
y 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完
x
x
x 次课。
输入格式
输入的第一行包含两个整数
n
,
x
n, x
n,x, 分别表示河的宽度和小青蛙需要去学校的天数。请注意
2
x
2x
2x 才是实际过河的次数。
第二行包含
n
−
1
n-1
n−1 个非负整数
H
1
,
H
2
,
⋯
,
H
n
−
1
H_{1}, H_{2}, \cdots, H_{n-1}
H1,H2,⋯,Hn−1, 其中
H
i
>
0
H_{i}>0
Hi>0 表示在河中与 小青蛙的家相距
i
i
i 的地方有一块高度为
H
i
H_{i}
Hi 的石头，
H
i
=
0
H_{i}=0
Hi=0 表示这个位置没有石头。
输出格式
输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。
样例 #1
样例输入 #1
5 1
1 0 1 0
样例输出 #1
4
提示
【样例解释】
由于只有两块高度为
1
1
1 的石头，所以往返只能各用一块。第
1
1
1 块石头和对岸的距离为
4
4
4，如果小青蛙的跳跃能力为
3
3
3 则无法满足要求。所以小青蛙最少需要
4
4
4 的跳跃能力。
【评测用例规模与约定】
对于
30
%
30 \%
30% 的评测用例，
n
≤
100
n \leq 100
n≤100;
对于
60
%
60 \%
60% 的评测用例，
n
≤
1000
n \leq 1000
n≤1000;
对于所有评测用例，
1
≤
n
≤
1
0
5
,
1
≤
x
≤
1
0
9
,
0
≤
H
i
≤
1
0
4
1 \leq n \leq 10^{5}, 1 \leq x \leq 10^{9}, 0 \leq H_{i} \leq 10^{4}
1≤n≤105,1≤x≤109,0≤Hi≤104 。
蓝桥杯 2022 省赛 A 组 F 题。
思路
分析题意后不难发现这题是要二分答案的，但关键在于check函数怎么写
由于往返x次与连续走2x次是等价的，因此我们可以试着大胆地去猜测一下结论
猜结论
结论:不存在高度之和小于2x的区间
当青蛙的最大跳跃步长为y时，我们假设存在某个长度为y的区间[l,r]
这2x次全程必定是需要经过这个区间2x次的。
假设存在某种走法可以不经过该区间，那么必定就有某一个的跳跃的步长超过r−l+1=y
这与题意矛盾。
这说明了若青蛙想要抵达对岸，就必须满足对于任意一个长度为y的区间，其高度之和都要大于等于2x
接下来只需要证明当每个区间和都大于等于2x
一定是成立的即可
由于每一个区间和都是大于等于2x的
因此对于任意一个点，当青蛙跳上来之后，都可以保证它的下一步有落脚点，这就说明了青蛙一定可以从起点跳至终点。
综上结论得证
因此check函数只需要判断是否每个区间的高度之和都是大于等于2x的就行了。
【代码块】
#include
#include
#include
using namespace std;
const int N = 1e5 + 10;
int s[N];
typedef long long ll;
ll n, x;
bool check(int m) {
for (int i = 1; i + m <= n; i++) {
if (s[i + m - 1] - s[i - 1] < 2 * x)
return false;
}
return true;
}
int main() {
cin >> n >> x;
for (int i = 1; i < n; i++) {
int a;
cin >> a;
s[i] = s[i - 1] + a;
}
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (check(mid))
r = mid;
else
l = mid + 1;
}
cout << l << endl;
return 0;
}
好文阅读
您阅读本篇文章共花了：
发表评论