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;
}

results matching ""

    No results matching ""