形式化题目

数轴上有 $n$ 个格子，坐标 $0 < x_1 < x_2 < \dots < x_n$，格子 $i$ 的分数为 $s_i$（可为负）。 机器人从原点出发，每一步必须向右跳并落在一个格子上；花 $g$ 个金币后，每一步的跳距可以在

内任意选取（$g=0$ 时区间退化为 $[d,d]$，即改造前的固定跳距 $d$）。机器人可以在任意格子结束游戏， 得分为所有落点格子的分数之和。求拿到至少 $k$ 分所需的最小 $g$；若不可能，输出 $-1$。

样例：$n=7,\ d=4,\ k=10$，格子依次为 $(2,6),(5,-3),(10,3),(11,-3),(13,1),(17,6),(20,2)$。 花 $2$ 个金币后跳距范围是 $[2,6]$，下面这条路线得 $15$ 分：

六跳全部落在 $[2,6]$ 内，总分 $6-3+3+1+6+2 = 15 \geqslant 10$；注意路线跳过了 $x=11$ 的 $-3$ 格—— 负分格可以跨过去不踩。下文的 DP 表会算出 $g=1$ 时最高只能拿 $9$ 分，因此答案恰为 $2$。

正解

思路

朴素做法：定 $g$ 后跑 $O(n^2)$ DP。 记 $lo = \max(1, d-g)$、$hi = d+g$，虚拟起点 $x_0=0,\ f_0=0$。 设 $f_i$ = 最后落在格子 $i$ 时的最高分，则

窗口为空则格子 $i$ 不可达；因为可以在任意格子结束，判定值就是 $\max_i f_i$。对每个 $i$ 扫描全部 $j<i$ 是 $O(n^2)$，$n = 5\times10^5$ 时约 $2.5\times10^{11}$ 次操作，不可行。

瓶颈不在 DP，而在"求窗内最大值"。 真正相关的前驱只有坐标落在 $[x_i-hi,\ x_i-lo]$ 里的格子—— 这是一个随 $i$ 变化的窗口；朴素写法把滑动窗口写成了全量扫描。又因为 $x_i$ 严格递增， 窗口两端 $x_i - hi$ 与 $x_i - lo$ 都随 $i$ 单调右移，于是可用滑动窗口 + 单调队列：

• 队列存下标，队内对应 $f$ 值保持递减；新格子入队前弹出队尾所有不比它大的 $f$ （这些下标从此不可能成为最大值）；
• 过期格子一定在队首——下标递增即坐标递增，队首坐标最小，坐标 $< x_i - hi$ 就出队；
• 于是队首恒为窗内最大 $f$，每次转移 $O(1)$ 摊还，整个判定 $O(n)$。

固定 $g$ 后在样例上的完整转移如下，表中同时给出 $g=1$ 与 $g=2$ 两列对照：

“窗"列是该格子的合法前驱坐标区间与实际选中的前驱，”—"表示窗内没有格子、该格不可达。 读表可见：$g=1$ 时窗口太窄，格子 1 和 4 够不着，$\max f_i = 9 < 10$ 判假； $g=2$ 时格子 7 拿到 $15 \geqslant 10$ 判真——这正是二分需要的单调判定。

对 $g$ 二分，并把区间封闭起来。 $g$ 越大，$lo$ 不增、$hi$ 不减，可行路线只增不减， $\max_i f_i$ 对 $g$ 单调不减，二分成立。两端这样取：

• 无解判据：每个格子至多踩一次，理论最高分 = 所有正分之和；它 $< k$ 时输出 $-1$。 题面样例 2 要 $20$ 分，正分和只有 $6+3+1+6+2 = 18 < 20$，因此输出 $-1$。
• 上界：依次踩上全部正分格子（负格全跳过）必是一条合法路线。设相邻间隔最大为 $\text{max\_gap}$（含起点到第一个正格），取 $g_{hi} = \max(d-1,\ \text{max\_gap} - d)$： $g_{hi} \geqslant d-1$ 使 $lo$ 缩到 $1$，盖住任何 $\geqslant 1$ 的间隔； $g_{hi} \geqslant \text{max\_gap} - d$ 使 $hi$ 覆盖最大间隔。此 $g$ 可行，答案必在 $[0, g_{hi}]$。

样例上：正分和 $18 \geqslant 10$，正格间隔 $\{2,8,3,4,3\}$ 给出 $g_{hi} = \max(3, 8-4) = 4$； 二分 $[0,4]$：$mid=2$ 真、$mid=1$ 假，得答案 $2$。

正确性要点：DP 满足最优子结构（以 $i$ 结尾的最优路线，其前缀必以某个窗内格子结尾且不劣）； 单调队列"下标递增、$f$ 递减"两条不变量保证队首始终是窗内最大值； 判定中任一 $f_i \geqslant k$ 即可提前返回（游戏可在任意格子结束）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG=-(ll)1000000000000000000LL;
bool check_g(ll g, vector<ll>&xs, vector<ll>&ss, ll d, ll k){ll lo=max(1LL,d-g), hi=d+g; int m=xs.size(); vector<ll> f(m,NEG); f[0]=0; deque<int> dq; int r=-1; for(int i=1;i<m;i++){ll right=xs[i]-lo; while(r+1<m && xs[r+1]<=right){r++; while(!dq.empty() && f[dq.back()]<=f[r]) dq.pop_back(); dq.push_back(r);} ll left=xs[i]-hi; while(!dq.empty() && xs[dq.front()]<left) dq.pop_front(); f[i]=(dq.empty()?NEG:f[dq.front()])+ss[i]; if(f[i]>=k) return true;} return false;}
ll min_coins(vector<ll>&xs,vector<ll>&ss,ll d,ll k){ll pos=0; for(int i=0;i<(int)ss.size();i++) if(ss[i]>0) pos+=ss[i]; if(pos<k) return -1; ll prev=0,maxgap=0; for(int i=0;i<(int)ss.size();i++) if(ss[i]>0){maxgap=max(maxgap,xs[i]-prev); prev=xs[i];} ll lo=0,hi=max(d-1,maxgap-d); while(lo<hi){ll mid=(lo+hi)/2; if(check_g(mid,xs,ss,d,k)) hi=mid; else lo=mid+1;} return lo;}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int n; ll d,k; if(!(cin>>n>>d>>k)) return 0; vector<ll> xs(1,0), ss(1,0); for(int i=0;i<n;i++){ll x,s;cin>>x>>s; xs.push_back(x); ss.push_back(s);} cout<<min_coins(xs,ss,d,k)<<'\n'; return 0;}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 13:01
# update_at: 2026-10-02 13:01

import sys
from collections import deque

NEG = -10**18  # 不可达哨兵：合法分数和最小只到 -n·max|s_i| = -5×10^10，哨兵区不会被误判


def check(g: int, xs: list[int], ss: list[int], d: int, k: int) -> bool:
    """花 g 个金币改造后能否拿到至少 k 分：单调队列滑窗 DP，够分即提前返回。"""
    lo = max(1, d - g)  # 改进后最短弹跳距离（题面规定至少为 1）
    hi = d + g          # 改进后最长弹跳距离
    m = len(xs)
    f = [NEG] * m
    f[0] = 0                    # 虚拟起点：位于 0，分数 0
    dq: deque[int] = deque()    # 窗内下标按 f 递减，队首就是窗内最高分
    r = -1                      # 已入队的最右下标；-1 表示虚拟起点还没入队
    for i in range(1, m):
        xi = xs[i]
        right = xi - lo         # 只有 xs[j] <= xi - lo 才跳得过来
        while r + 1 < m and xs[r + 1] <= right:
            r += 1
            while dq and f[dq[-1]] <= f[r]:  # 维持 f 单调递减
                dq.pop()
            dq.append(r)
        left = xi - hi          # xs[j] < xi - hi 的格子已经跳不到，出窗
        while dq and xs[dq[0]] < left:
            dq.popleft()
        f[i] = (f[dq[0]] if dq else NEG) + ss[i]  # 哨兵区加分数仍是哨兵区
        if f[i] >= k:           # 游戏可在任意格子结束，够分即可停
            return True
    return False


def min_coins(xs: list[int], ss: list[int], d: int, k: int) -> int:
    """二分最少金币数：正分总和不足 k 直接无解，否则在「依次访问全部正格」的上界内二分。"""
    pos_sum = sum(s for s in ss if s > 0)  # 只访问正格、跳过负格的最高分
    if pos_sum < k:
        return -1

    # 上界：依次访问所有正格时，g 要让 [max(1, d-g), d+g] 盖住起点到各正格的每个间隔
    prev, max_gap = 0, 0
    for i, s in enumerate(ss):
        if s > 0:
            max_gap = max(max_gap, xs[i] - prev)
            prev = xs[i]
    lo_g, hi_g = 0, max(d - 1, max_gap - d)  # d-1 让下界缩到 1，max_gap-d 让上界够长

    while lo_g < hi_g:
        mid = (lo_g + hi_g) // 2
        if check(mid, xs, ss, d, k):
            hi_g = mid
        else:
            lo_g = mid + 1
    return lo_g


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, d, k = next(data), next(data), next(data)
    xs, ss = [0], [0]
    for _ in range(n):
        x = next(data)
        s = next(data)
        xs.append(x)
        ss.append(s)
    print(min_coins(xs, ss, d, k))


if __name__ == "__main__":
    solve()

复杂度

• 时间：单次判定 $O(n)$（双指针 + 单调队列，每个下标至多进出队各一次）， 二分 $O(\log G)$ 次（$G \leqslant \max(d-1, x_n) \leqslant 10^9$，至多约 31 次）， 合计 $O(n \log G)$，与标准 C++ 解法同阶。实测 $n = 5\times10^5$ 的数据本地 0.6–0.8s； OJ 时限 1000ms，Python 存在 TLE 风险，但算法复杂度不降级。
• 空间：$O(n)$，三个长度 $n{+}1$ 的数组加单调队列。
• 同样的算法在 C++ 里用 vector<long long> 存 $f$、std::deque<int> 做单调队列即可； $f$ 的范围约 $\pm 5\times10^{10}$，需 long long。

总结

• 题目 = “定 $g$ 判定” + "对 $g$ 二分"两层：判定层是线性 DP，二分层靠区间单调性。
• 朴素 $O(n^2)$ 的瓶颈是全量扫前驱；观察到转移窗口随 $i$ 单调滑动后， 单调队列把判定压到 $O(n)$，总复杂度 $O(n \log G)$。
• $-1$ 与二分上界都来自"只踩正格"这条构造性路线：正分和给出无解判据， 正格最大间隔给出可行上界 $g_{hi} = \max(d-1, \text{max\_gap} - d)$。
• 跳距下界是 $\max(1, d-g)$ 而不是 $1$：样例中 $g=1$ 只能拿 $9$ 分正是这个下界卡出来的。