思路与算法

二分金币g。固定g后，允许跳距为[L,R]=[max(1,d-g),d+g]。dp[i]为停在第i格的最大分数，从坐标落在[x_i-R,x_i-L]的前驱dp最大值转移。用不回退的加入指针和单调队列维护窗口最优；起点(0,0)作为状态。若任意dp≥k就可行。先检验正分总和，连它都小于k则无解。

正确性说明

固定g时每条合法跳跃从更左状态到当前状态，窗口精确等于所有合法前驱，取最大并加当前分数给出最佳路径。单调队列仅丢弃已过窗口的点，以及被更晚且分数不低点支配的前驱，因此保留最优。增加g只扩大跳距集合，可行性单调；g达到max(d,x_n)后所有向右跨格都允许，能选全部正分，故正分总和也给出完整无解判定。二分求最小可行g。

复杂度

O(n log(max(d,x_n)+1))时间、O(n)空间，含每次判定dp和队列初始化。

易错点

格子分数可负，不能贪心只接相邻可达点；总分用64位。起点必须能作为前驱，最小跳距始终至少1，不允许停在原处。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, d;
    long long k;
    cin >> n >> d >> k;
    vector<int> x(n + 1), s(n + 1);
    long long possible = 0;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> s[i];
        possible += max(0, s[i]);
    }
    if (possible < k) {
        cout << -1 << "\n";
        return 0;
    }
    auto check = [&](int g) {
        int L = max(1, d - g), R = d + g, add = 0;
        vector<long long> dp(n + 1, LLONG_MIN / 4);
        dp[0] = 0;
        deque<int> q;
        for (int i = 1; i <= n; i++) {
            while (add < i && x[add] <= x[i] - L) {
                if (dp[add] > LLONG_MIN / 4) {
                    while (!q.empty() && dp[q.back()] <= dp[add])
                        q.pop_back();
                    q.push_back(add);
                }
                add++;
            }
            while (!q.empty() && x[q.front()] < x[i] - R)
                q.pop_front();
            if (!q.empty())
                dp[i] = dp[q.front()] + s[i];
            if (dp[i] >= k)
                return true;
        }
        return false;
    };
    int l = 0, r = max(d, x[n]);
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << "\n";
}