1. 2026: [蓝桥杯2022初赛] 青蛙过河
传送门:http://oj.ecustacm.cn/problem.php?id=2026
1.1. 题意
小青蛙住在一条河边,它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。河里的石头排成了一条直线,小青蛙每次跳跃必须落在一块石头或者岸上。不过,每块石头有一个高度,每次小青蛙从一块石头起跳,这块石头的高度就会下降,当石头的高度下降到时小青蛙不能再跳到这块石头上(某次跳跃后使石头高度下降到 是允许的)。
小青蛙一共需要去学校上天课,所以它需要往返次。当小青蛙具有一个跳跃能力时,它能跳不超过的距离。请问小青蛙的跳跃能力至少是多少才能用这些石头上完次课。
1.2. Tag
二分答案、贪心
1.3. 难度
☆☆☆☆
1.4. 思路
往返累计次相当于单向走次。跳跃能力越大,越能保证可以通过次。因此可以使用二分答案,找到一个最小的满足条件的跳跃能力。
假设跳跃能力为,一种思想是每次能跳多远跳多远,然后去模拟判断是否合法,做法比较复杂,暂不展开。
另一种想法是判断每个长度为的区间之和是否大于等于,如果每个区间和都大于,肯定可以保证构造出一组解通过次。反过来是否成立可以自行思考一下。参考:https://www.zhihu.com/question/525176453/answer/2433729894
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
template <typename T>
inline T read(T& x) {
x = 0;
T w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
int h[maxn], sum[maxn];
int n, x;
//判断所有长度为mid的区间之和是否大于等于2x
bool check(int mid){
for(int i = 1; i + mid - 1 <= n; i++)
if(sum[i + mid - 1] - sum[i - 1] < 2 * x)return false;
return true;
}
int main(){
read(n); read(x);
for(int i = 1; i <= n - 1; i++)//预处理前缀和
read(h[i]), sum[i] = sum[i - 1] + h[i];
sum[n] = 1e9 + 7;
int left = 1, right = n, ans = n;
while(left <= right)//二分答案
{
int mid = (left + right) >> 1;
if(check(mid))
ans = mid, right = mid - 1;//求最小合法解
else
left = mid + 1;
}
cout<<ans<<endl;
return 0;
}