每时刻只能原地或向右一格,求最多能"恰好"接住多少枚金币。
数轴上会出现 n 枚金币,第 i 枚金币将在时刻 tᵢ 出现在坐标 xᵢ。小 A 必须在时刻 tᵢ 恰好位于坐标 xᵢ,才能获得这枚金币。
游戏开始时为时刻 0,小 A 的坐标为 0。游戏机的左方向键失灵了,小 A 每个时刻只能选择"保持不动"或"向右移动一个单位"。换言之,若时刻 t 在坐标 x,则时刻 t + 1 的坐标只能是 x 或 x + 1。
求最多能收集的金币数量。
v = t − x——v 就是"在该点能富余出多少等待时间"。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 |
xᵢ ≤ xⱼ(只能向右,不能回头),且 tⱼ − tᵢ ≥ xⱼ − xᵢ(时间必须够走这段路)vᵢ = tᵢ − xᵢ?因为 tⱼ − tᵢ ≥ xⱼ − xᵢ ⟺ (xⱼ + vⱼ) − (xᵢ + vᵢ) ≥ xⱼ − xᵢ ⟺ vᵢ ≤ vⱼ。条件瞬间被化简成两个"不降"关系tⱼ ≥ tᵢ 不用单独判断?tⱼ − tᵢ = (xⱼ − xᵢ) + (vⱼ − vᵢ) ≥ 0 由两个不降条件自动推出,不用额外检查tᵢ < xᵢ(即 vᵢ < 0)的金币永远到不了,先过滤掉(x, v) 升序排序,对 v 序列求最长不下降子序列,用二分贪心做到 O(n log n)输入:3,金币为 A(1, 6)、B(3, 7)、C(2, 4)(格式:坐标 x, 时刻 t)。
| 金币 | 坐标 x | 时刻 t | v = t − x | 起点能到吗 |
|---|---|---|---|---|
| A | 1 | 6 | 5 | 能(5 ≥ 0) |
| B | 3 | 7 | 4 | 能(4 ≥ 0) |
| C | 2 | 4 | 2 | 能(2 ≥ 0) |
三枚金币的 v 都非负,全部保留。按 (x, v) 升序排序后得到的 v 序列是 [5, 2, 4](对应 A、C、B)。
| 排序后位置 | 金币 | x | v | 以它结尾的最长长度 |
|---|---|---|---|---|
| 1 | A | 1 | 5 | 1 |
| 2 | C | 2 | 2 | 1 |
| 3 | B | 3 | 4 | 2 |
最长不下降子序列长度 = 2(取 C → B)✓
按 v 序列 [5, 2, 4] 看:
A 的 v = 5,排在它后面的 C、B 的 v 分别是 2、4
要接在 A 后面必须满足 v ≥ 5,但 2 和 4 都 < 5 ✗
所以只要拿了 A,后面就再也接不上任何金币
✅ A 与 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ᵢ = tᵢ − xᵢ 就是还能站着等多久。输入:4,金币为 (1, 1)、(2, 2)、(1, 3)、(2, 4)。
| 金币 | 坐标 x | 时刻 t | v = t − x |
|---|---|---|---|
| (1, 1) | 1 | 1 | 0 |
| (2, 2) | 2 | 2 | 0 |
| (1, 3) | 1 | 3 | 2 |
| (2, 4) | 2 | 4 | 2 |
按 (x, v) 升序排序后,v 序列为 [0, 2, 0, 2]。
| 排序后位置 | 金币 | x | t | v | 以它结尾的最长长度 |
|---|---|---|---|---|---|
| 1 | (1, 1) | 1 | 1 | 0 | 1 |
| 2 | (1, 3) | 1 | 3 | 2 | 2 |
| 3 | (2, 2) | 2 | 2 | 0 | 2 |
| 4 | (2, 4) | 2 | 4 | 2 | 3 |
最长不下降子序列长度 = 3(取 (1,1) → (1,3) → (2,4))✓
时刻 1 在坐标 1 → 拿到 (1, 1)
时刻 2、3 原地不动(在坐标 1)→ 拿到 (1, 3)
时刻 4 向右走 1 格到坐标 2 → 拿到 (2, 4)
共 3 枚 ✓
✅ 3 枚
剩下的是 (2, 2):时刻 2 必须站在坐标 2
同一时刻只能在一个坐标,二者只能取其一
若先拿 (2, 2),时刻 3 就再也回不到坐标 1(不能向左)
所以 (2, 2) 与 (1, 3) 冲突,只能二选一
✅ 上限就是 3
过滤 v < 0 → 按 (x, v) 排序 → 对 v 求 LNDS(二分贪心)
直接按定义 dp[j] = max(dp[i] + 1),i 遍历所有能接到 j 的金币
dp[j] = max(dp[i] + 1),条件 xᵢ ≤ xⱼ 且 vᵢ ≤ vⱼ),再发现它正是二维 LIS,于是用排序 + 二分优化到 O(n log n)。先写对再提速,是优化题的标准路径。| 方案 | 复杂度 | n = 10⁵ 时的运算量 |
|---|---|---|
| 排序 + LNDS | O(n log n) | ≈ 1.7 × 10⁶ ✅ |
| 二维 DP | O(n²) | ≈ 10¹⁰ ❌ 超时 |
| 按 t 排序后贪心 | O(n log n) | ❌ 会"走过头"回不来,反例见上文 |
第一行输入 n,随后 n 行每行 x t(坐标与时刻)。程序会过滤掉到不了的金币,按 (x, v) 排序后求最长不下降子序列。
点按钮开始 →
#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 更稳。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 2 | 题面样例 1:取 (2,4) → (3,7) |
4 | 3 | 题面样例 2:取 (1,1) → (1,3) → (2,4) |
1 | 0 | v = 1 − 2 = −1 < 0,起点走不到,一枚也拿不到 |
3 | 3 | 三枚完全相同的金币 → 必须用"不下降"才能全拿 |
2 | 1 | v 序列 [3, 0] 无法同时不降,最多 1 枚 |
2 | 2 | 极值规模:(1,1) 后再走 999999999 格刚好赶上 |
t < x(即 v < 0)的金币永远到不了,必须在排序前剔除。upper_bound(允许相等);写成 lower_bound 时重复金币只算 1 枚。(x, v) 双关键字升序,只按 x 排序会让同 x 的金币顺序不稳定。存 (x, v) 数对需要 O(n);二分用的 tails 数组最长也是 O(n)。
✅ 约 170 万次操作,1 秒内非常轻松。本题的难点不在速度,而在于把"时刻 + 坐标"两个约束化简成 (x, v) 的二维偏序——想通这一点,代码只有 25 行。
// —— 最长不下降子序列(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 的"方案还原"是个高频考点,值得记牢。)