洛谷P8775 [藍橋杯 2022 省 A] 青蛙過河 題解 貪心+二分答案

題目連結

​​https://www.luogu.com.cn/problem/P8775​​

題目大意

小青蛙住在一條河邊，它想到河對岸的學校去學習。小青蛙打算經過河裡的石頭跳到對岸。

河裡的石頭排成了一條直線，小青蛙每次跳躍必須落在一塊石頭或者岸上。不過，每塊石頭有一個高度，每次小青蛙從一塊石頭起跳，這塊石頭的高度就會下降 \(1\)，當石頭的高度下降到 \(0\) 時小青蛙不能再跳到這塊石頭上（某次跳躍後使石頭高度下降到 \(0\)

小青蛙一共需要去學校上 \(x\) 天課，是以它需要往返 \(2x\) 次。當小青蛙具有一個跳躍能力 \(y\) 時，它能跳不超過 \(y\)

請問小青蛙的跳躍能力至少是多少才能用這些石頭上完 \(x\)

解題思路

不妨看一下 ​​CF965D Single-use Stones​​ 這道題，然後你就會發現兩道題目幾乎一摸一樣。

本題隻是在 CF965D 的基礎上加了一個二分。

兩道題最主要要解決的問題都是一樣的，就是：

如何計算當跳躍能力為 \(k\)

解決這個問題的方法有很多，我使用的是 貪心，思路是這樣的：

當跳躍能力為 \(k\) 時，對于第 \(i\) 塊石頭，能跳到它的石頭對應的區間是 \([i-k, i-1]\)，此時必然優先選下标小的。為什麼呢？因為如果 \(i-k\) 和 \(i-k+1\) 都可以選擇，我選擇 \(i-k\) 必然更優，因為留下來的 \(i-k+1\) 還可以跳到第 \(i+1\) 個石頭，但是如果留下來 \(i-k\)，是不能跳到第 \(i+1\) 個石頭的。是以，對于第 \(i\) 塊石頭，優先選擇下标 \(i\)

那麼，同樣的道理反過來思考，如果我目前在第 \(i\) 個石頭，我能夠跳到的石頭的區間範圍是 \([i+1, i+k]\)，我也會優先選擇下标大的那個石頭跳過去。

是以可以設計一個 ​

​cal(k)​

​ 函數，其傳回跳躍能力為 \(k\)

示例程式

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;

int n, x, h[maxn], c[maxn];

int cal(int k) {
    memset(c, 0, sizeof(int)*(n+1));
    h[0] = c[0] = h[n] = 2e9;
    stack<int> stk;
    for (int i = 1; i < k; i++) stk.push(i);
    for (int i = 0; i < n; i++) {
        if (i+k <= n && h[i+k]) stk.push(i+k);
        while (c[i] && !stk.empty() && stk.top() > i) {
            int j = stk.top();
            // i --> j
            int t = min(c[i], h[j] - c[j]);
            c[i] -= t;
            c[j] += t;
            if (c[j] == h[j]) stk.pop();
        }
    }
    return c[n];
}

int main() {
    cin >> n >> x;
    for (int i = 1; i < n; i++) cin >> h[i];
    int l = 1, r = n, res;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (cal(mid) >= 2 * x) {
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << res << endl;
    return 0;
}