题目

小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。

河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃 后使石头高度下降到 0 是允许的)。

小青蛙一共需要去学校上 $x$ 天课, 所以它需要往返 $2x$次。当小青蛙具有 一个跳跃能力 $y$ 时, 它能跳不超过 $y$的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 $x$ 次课。

输入格式

输入的第一行包含两个整数$n,x$, 分别表示河的宽度和小青蛙需要去学校 的天数。请注意$2x$ 才是实际过河的次数。

第二行包含 $n−1$ 个非负整数$H_1,H_2,⋯,H_{n−1}$, 其中 $H_i$>0 表示在河中与小青蛙的家相距 $i$的地方有一块高度为 $H_i$ 的石头,$H_i=0$ 表示这个位置没有石头。

输出格式

输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。

样例输入

5 1
1 0 1 0

样例输出

4

样例说明

由于只有两块高度为 1 的石头，所以往返只能各用一块。第 1 块石头和对岸的距离为 4，如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4 的跳跃能力。

评测用例规模与约定

对于 30% 的评测用例, $n≤100$;

对于 60% 的评测用例, $n≤1000$;

对于所有评测用例, $1≤n≤10^5,1≤x≤10^9,1≤H_i≤10^4 $。

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 512M

解答

  • 常规思路

一只青蛙上x次课，来回走了2x次；相当于2x只青蛙上了一次课（只走一段）；每次踩石头它的高度都下降1，而且青蛙都能过河。所以可以先求前缀和之后二分法进行贪心的求解，代码的思路如下：

  1. 定义数组的最大长度N，整型数字n,m，数组a用于接收输入，数组b用于计算前缀和;
  2. 得到n，m和数组a之后，定义数组a[0] = a[n] = N,然后进行计算前缀和的操作。例如前缀和b[i]=x的意思就是i之前的石头一共可以容纳x个青蛙跳过(我们一共需要2m)个;
  3. 进行二分+贪心操作，求出最小的跳跃能力值。
  4. check函数用于计算在x的下标下，石头是否能让2m个青蛙通过。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 3;
ll a[N],b[N];
int n, m;
bool check(int x) {
    for(int i = 1; i + x - 1 < n ;i++) {
        // 只有一个的时候
        if (b[i + x - 1] - b[i - 1] < 2 * m) {
            // 石块为0的情况
            return false;
        }
    }
    return true;
}
int main(){
    cin >> n >> m;
    for(int i = 1; i < n; i++) {
        // 循环到n-1
        cin >> a[i];
    }
    a[0] = a[n] = N;
    for (int i = 1; i < n; i++) {
        // 计算前缀和
        b[i] = b[i - 1] + a[i]; // 我能让几只小青蛙在上面
    }
    // 贪心求y
    int l = 1, r = N;
    while (l < r){
        int mid = (l + r) / 2;
        if (check(mid)) { // 石头足够青蛙分，继续贪心
            r = mid;
        }
        else { // 石头不够青蛙分
            l = mid + 1;
        }
    }
    cout << l;
    return 0;
}