GESP 题解库 / 7 级题解 / [GESP202509 七级] 金币收集 · 第 5 / 24 题
GESP202509 七级 · P14078 · 困难

金币收集

每时刻只能原地或向右一格,求最多能"恰好"接住多少枚金币。

📊
n ≤ 10⁵
金币数量
🔢
x, t ≤ 10⁹
坐标与时刻
⚡
O(n log n)
时间复杂度
🎯
二维偏序 + LNDS
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

数轴上会出现 n 枚金币,第 i 枚金币将在时刻 tᵢ 出现在坐标 xᵢ。小 A 必须在时刻 tᵢ 恰好位于坐标 xᵢ,才能获得这枚金币。

游戏开始时为时刻 0,小 A 的坐标为 0。游戏机的左方向键失灵了,小 A 每个时刻只能选择"保持不动"或"向右移动一个单位"。换言之,若时刻 t 在坐标 x,则时刻 t + 1 的坐标只能是 x 或 x + 1。

求最多能收集的金币数量。

💡
人话翻译:小 A 一直从 (0, 0) 出发向右"爬"(可以原地等),要让他经过尽可能多的金币点。
关键观察:如果从 (0,0) 走到 (x,t) 至少需要 x 个时刻,所以推出新量 v = t − x——v 就是"在该点能富余出多少等待时间"。
能先拿 i 再拿 j,等价于 xᵢ ≤ xⱼ 且 vᵢ ≤ vⱼ,于是问题变成二维偏序的最长链:排序后对 v 求最长不下降子序列。

🔍 关键词提取

二维偏序最长不下降子序列排序 + 二分坐标变换贪心的陷阱

已知条件

项目说明
输入第一行 n;随后 n 行每行 xᵢ、tᵢ(坐标、时刻)
输出最多能收集的金币数量
数据范围1 ≤ n ≤ 10⁵,1 ≤ xᵢ, tᵢ ≤ 10⁹
起点时刻 0、坐标 0
移动规则每个时刻只能"不动"或"向右 + 1"
获得条件必须在时刻 tᵢ 恰好位于坐标 xᵢ
40% 部分分1 ≤ n ≤ 8

需要解决的问题

02
思维导图
整理解题思路的全貌
🪙 能先拿 i 再拿 j ⟺ xᵢ ≤ xⱼ 且 vᵢ ≤ vⱼ(v = t − x)
🧠 坐标变换
令 vᵢ = tᵢ − xᵢ
v 表示"到达该点后能等待多久"
v < 0 → 起点到不了,直接丢掉
两个不降条件 ⇔ 可以先后拿到
📐 算法流程
过滤 v < 0 的金币
按 (x, v) 升序排序
对 v 求最长不下降子序列
二分维护 tails,O(n log n)
🔁 为什么用"不下降"
x 与 v 都相同的金币在同一时刻同一点
"恰好同时"就能全拿走
所以相等时允许接在后面
换成"严格上升"就会漏掉重复金币
⚠️ 易错点
忘了过滤 v < 0(起点到不了)
用了"严格上升"导致重复金币只算 1
只按 t 排序后贪心(会走过头回不来)
排序键写成 (v, x) 顺序反了
03
样例手算推导
两个样例的完整推演

🧮 样例 1:3 枚金币,答案 2

输入:3,金币为 A(1, 6)、B(3, 7)、C(2, 4)(格式:坐标 x, 时刻 t)。

金币坐标 x时刻 tv = t − x起点能到吗
A165能(5 ≥ 0)
B374能(4 ≥ 0)
C242能(2 ≥ 0)

三枚金币的 v 都非负,全部保留。按 (x, v) 升序排序后得到的 v 序列是 [5, 2, 4](对应 A、C、B)。

排序后位置金币xv以它结尾的最长长度
1A151
2C221
3B342

最长不下降子序列长度 = 2(取 C → B)✓

1
为什么不能三枚全拿

按 v 序列 [5, 2, 4] 看:

A 的 v = 5,排在它后面的 C、B 的 v 分别是 2、4

要接在 A 后面必须满足 v ≥ 5,但 2 和 4 都 < 5 ✗

所以只要拿了 A,后面就再也接不上任何金币

✅ A 与 B 无法共存

2
C → B 这条链为什么可行

C:x = 2, v = 2 → 时刻 t = 2 + 2 = 4,坐标 2

从 (0, 0) 出发:4 个时刻向右走 2 格 ✓ 到达

B:x = 3, v = 4 → 时刻 t = 3 + 4 = 7,坐标 3

从 (2, 4) 到 (3, 7):差 1 格、差 3 个时刻,够用 ✓

两个不降条件:x 满足 2 ≤ 3,v 满足 2 ≤ 4 ✓

✅ 共 2 枚

🔑
把 v 理解成"时间余额":走 1 格要花 1 个时刻,所以到达 xᵢ 时已经花掉了 xᵢ 个时刻,vᵢ = tᵢ − xᵢ 就是还能站着等多久。
"先 i 后 j 能成功"就是要求余额不能变少(vᵢ ≤ vⱼ)——余额可以增加(路上可以原地等),但绝不能"透支"。这就是为什么等价于不下降。

🧮 样例 2:4 枚金币,答案 3

输入:4,金币为 (1, 1)、(2, 2)、(1, 3)、(2, 4)。

金币坐标 x时刻 tv = t − x
(1, 1)110
(2, 2)220
(1, 3)132
(2, 4)242

按 (x, v) 升序排序后,v 序列为 [0, 2, 0, 2]。

排序后位置金币xtv以它结尾的最长长度
1(1, 1)1101
2(1, 3)1322
3(2, 2)2202
4(2, 4)2423

最长不下降子序列长度 = 3(取 (1,1) → (1,3) → (2,4))✓

1
最优的 3 枚怎么走

时刻 1 在坐标 1 → 拿到 (1, 1)

时刻 2、3 原地不动(在坐标 1)→ 拿到 (1, 3)

时刻 4 向右走 1 格到坐标 2 → 拿到 (2, 4)

共 3 枚 ✓

✅ 3 枚

2
为什么第 4 枚拿不到

剩下的是 (2, 2):时刻 2 必须站在坐标 2

同一时刻只能在一个坐标,二者只能取其一

若先拿 (2, 2),时刻 3 就再也回不到坐标 1(不能向左)

所以 (2, 2) 与 (1, 3) 冲突,只能二选一

✅ 上限就是 3

⚠️
这里最容易踩的坑是"t 排序 + 贪心拿":按时刻从小到大扫,能拿就拿,这样的贪心是错的。
反例:金币 (4, 4)、(1, 5)、(2, 6)。贪心先拿 (4, 4) 走到坐标 4,而后两枚都在坐标 ≤ 2,再也回不去了,只拿到 1 枚;而正确做法是放弃 (4, 4),拿 (1, 5) 与 (2, 6),共 2 枚。
所以必须老老实实做二维偏序的最长链。
04
解法对比
排序 + LNDS vs 二维 DP / 按时刻贪心

⚔️ 解法对比

🟢 排序 + 最长不下降子序列(推荐) 推荐

过滤 v < 0 → 按 (x, v) 排序 → 对 v 求 LNDS(二分贪心)

  • 时间 O(n log n)
  • n = 10⁵ 时约 1.7 × 10⁶
  • 代码约 25 行
  • 空间 O(n)
💡
为什么排序后只需看 v 这一维?排序已经让 x 单调不降了,剩下的只要保证 v 也不降,两个条件就同时满足。
这就是经典的"二维偏序 → 一维 LIS"降维套路。

🟠 二维 DP

直接按定义 dp[j] = max(dp[i] + 1),i 遍历所有能接到 j 的金币

  • 时间 O(n²)
  • n = 10⁵ 时是 10¹⁰
  • 必然超时
  • 只能在 n ≤ 8 / n ≤ 100 的部分分里用
⚠️
DP 是理解本题的钥匙:先把 DP 写出来(转移是 dp[j] = max(dp[i] + 1),条件 xᵢ ≤ xⱼ 且 vᵢ ≤ vⱼ),再发现它正是二维 LIS,于是用排序 + 二分优化到 O(n log n)。先写对再提速,是优化题的标准路径。

📈 性能对比

方案复杂度n = 10⁵ 时的运算量
排序 + LNDSO(n log n)≈ 1.7 × 10⁶ ✅
二维 DPO(n²)≈ 10¹⁰ ❌ 超时
按 t 排序后贪心O(n log n)❌ 会"走过头"回不来,反例见上文
05
算法流程图
过滤 → 排序 → 求最长不下降子序列
开始读入 n 以及 n 枚金币的 (xᵢ, tᵢ)计算 vᵢ = tᵢ − xᵢ;若 vᵢ < 0 则直接丢弃把剩下的 (xᵢ, vᵢ) 按 (x, v) 升序排序准备空数组 tails,逐枚扫描金币tails 中存在"大于当前 v"的元素吗?存在 ✓把第一个大于 v 的位置替换成 v(不改变长度)不存在 ✗把 v 追加到 tails 末尾,长度加 1输出 tails 的长度处理下一枚金币
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🪙 最多能收集几枚金币

第一行输入 n,随后 n 行每行 x t(坐标与时刻)。程序会过滤掉到不了的金币,按 (x, v) 排序后求最长不下降子序列。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(过滤 + 排序 + 最长不下降子序列)

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

int main() {
    int n;
    scanf("%d", &n);

    vector<pair<long long, long long>> pts;   // (x, v)
    for (int i = 0; i < n; i++) {
        long long x, t;
        scanf("%lld %lld", &x, &t);
        long long v = t - x;                  // 关键量:时间余额
        if (v < 0) continue;                  // 起点到不了,直接扔掉
        pts.push_back({x, v});
    }

    sort(pts.begin(), pts.end());             // 先按 x 升序,x 相同再按 v 升序

    // tails[k] = 长度 k + 1 的不下降子序列的"最小结尾"
    vector<long long> tails;
    for (auto &p : pts) {
        long long v = p.second;
        // upper_bound:找第一个"大于 v"的位置 => 允许相等,即"不下降"
        int pos = (int)(upper_bound(tails.begin(), tails.end(), v) - tails.begin());
        if (pos == (int)tails.size()) tails.push_back(v);
        else                          tails[pos] = v;
    }

    printf("%d\n", (int)tails.size());
    return 0;
}
🔑
为什么这里用 upper_bound 而不是 lower_bound?
upper_bound 找的是"第一个 大于 v"的位置,所以等于 v 的元素会被忽略,当前 v 就能接在它们后面 → 允许相等 → 不下降。
若改用 lower_bound(第一个 ≥ v),相等的元素会被替换掉,就变成了严格上升,同一时刻同一坐标的多枚金币只会算到 1 枚。

📖 关键几行怎么看

代码作用为什么这样写
long long v = t - x;坐标变换把"两个不降条件"浓缩成一个 v 的不降
if (v < 0) continue;过滤t < x 时从 (0,0) 根本走不到
sort(pts.begin(), pts.end());排序pair 默认先比 first(x) 再比 second(v)
upper_bound(tails.begin(), tails.end(), v)二分允许相等 ⟹ 最长"不下降"子序列
tails.push_back(v)延长找不到更大的结尾,说明可以接在最长的链后面
⚠️
四个坑:① 忘记过滤 v < 0 的金币,把它们排进序列会算出偏大的错误答案;② 把 upper_bound 写成 lower_bound,退化成"严格上升",重复金币被吃掉;③ 排序只按 x(v 也要参与,否则同 x 的金币顺序不确定,可能漏掉更优解);④ 全程只用 int 虽然本题 10⁹ 勉强够,但 t + v 这类中间量建议统一用 long long 更稳。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
1 6
3 7
2 4
2题面样例 1:取 (2,4) → (3,7)
4
1 1
2 2
1 3
2 4
3题面样例 2:取 (1,1) → (1,3) → (2,4)
1
2 1
0v = 1 − 2 = −1 < 0,起点走不到,一枚也拿不到
3
1 5
1 5
1 5
3三枚完全相同的金币 → 必须用"不下降"才能全拿
2
3 3
1 4
1v 序列 [3, 0] 无法同时不降,最多 1 枚
2
1 1
1000000000 1000000000
2极值规模:(1,1) 后再走 999999999 格刚好赶上
✅
自查清单:① 过滤了 v < 0 吗?② 用的是不下降(upper_bound)吗?③ 排序键是 (x, v) 吗?④ 复杂度是 O(n log n) 而不是 O(n²) 吗?

🚨 易错点清单

⚠️
忘记过滤:t < x(即 v < 0)的金币永远到不了,必须在排序前剔除。
⚠️
用成"严格上升":必须用 upper_bound(允许相等);写成 lower_bound 时重复金币只算 1 枚。
⚠️
按时刻贪心:"能拿就拿"会走过头,反例 (4,4)、(1,5)、(2,6) 贪心得 1、正解得 2。
⚠️
排序键不全:必须按 (x, v) 双关键字升序,只按 x 排序会让同 x 的金币顺序不稳定。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log n)
空间复杂度
O(n)
n 最大
10⁵
运算量
约 1.7 × 10⁶

时间怎么算的?

空间都用在哪?

存 (x, v) 数对需要 O(n);二分用的 tails 数组最长也是 O(n)。

✅ 约 170 万次操作,1 秒内非常轻松。本题的难点不在速度,而在于把"时刻 + 坐标"两个约束化简成 (x, v) 的二维偏序——想通这一点,代码只有 25 行。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// —— 最长不下降子序列(LNDS,允许相等)——
vector<long long> tails;
for (long long v : arr) {
    int pos = upper_bound(tails.begin(), tails.end(), v) - tails.begin();
    if (pos == (int)tails.size()) tails.push_back(v);
    else                          tails[pos] = v;
}
// 答案 = tails.size()

// —— 对照:最长严格上升子序列(LIS)——
// 只把 upper_bound 换成 lower_bound 即可

// —— 本题的坐标变换 ——
// v = t - x
// 能先 i 后 j  ⟺  x_i ≤ x_j  且  v_i ≤ v_j
//   (x_i ≤ x_j:不能向左走)
//   (v_i ≤ v_j:由 t_j - t_i ≥ x_j - x_i 化简而来)
// t_j ≥ t_i 会自动成立,不必单独判断

// —— 若还要输出具体方案 ——
// 在 DP 里记录前驱 pre[],最后从最优结尾回溯即可(模拟器就是这么做的)

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
坐标变换用 v = t − x 把两个约束压成一个任何"时间 + 位置"的到达类问题
二维偏序 → LIS排序一维,另一维求最长子序列导弹拦截、矩形嵌套、最长链
不下降 vs 严格上升依题意选 upper_bound / lower_bound重复元素计数、相等可共存的问题
先 DP 后优化O(n²) DP 想清楚,再用二分降到 O(n log n)一切需要"先对再快"的题
🌟
思考题:本题只问"最多几枚"。如果还要你输出其中一个最优的拿取顺序,算法要加什么?(提示:几乎不用改——在求最长不下降子序列时,给每个元素记一个"前驱下标" pre[j],记录它是从哪个 i 转移来的;最后从"最优结尾"沿 pre 一路回溯,就得到了一条最优链。页面上的模拟器正是这么实现的,加粗的 ✓ 就是回溯出来的链路。LIS/LNDS 的"方案还原"是个高频考点,值得记牢。)