金币收集题解

一、题目分析

我们有 $n$ 枚金币，第 $i$ 枚金币在时刻 $t_i$ 出现在坐标 $x_i$ 。小 A 一开始在时刻 $0$ 位于坐标 $0$ ，每一秒钟只能不动或者向右移动一个单位。他必须在某个金币出现的同一时刻到达该坐标，才能收集这枚金币。

游戏过程中，小 A 的坐标只会增加或不变。因此，如果他想收集坐标为 $x_i$ 的金币，他从起点出发，至少需要 $x_i$ 步向右移动，不能在 $t_i$ 小于 $x_i$ 时到达。于是，第一个必要条件就是 $t_i \ge x_i$ 。显然， $t_{i} < x_{i}$ 的金币无论如何也拿不到，可以直接忽略。

接下来考虑收集多枚金币的先后顺序。假设小 A 在时刻 $t_1$ 收集了位于 $x_1$ 的金币，然后又想在时刻 $t_2$ 收集位于 $x_2$ 的金币，则需要满足：

时间顺序： $t_{1} < t_{2}$ （严格小于，同一时刻只能在一个坐标）；
空间顺序： $x_1 \le x_2$ （因为不能向左移动）；
速度限制：在 $(t_2 - t_1)$ 的时间里，小 A 最多向右移动 $(t_2 - t_1)$ 个单位，因此必须满足 $x_2 - x_1 \le t_2 - t_1$ 。

整理一下：对于可行的先后金币对 $(x_1,t_1)$ 和 $(x_2,t_2)$ ，必有：

x_{1} \leq x_{2} 且 t_{1} \leq t_{2} 且 t_{2} - x_{2} \geq t_{1} - x_{1}

换句话说，一个合法的金币收集序列，按时间排序后，其坐标和“净等待时间” $t-x$ 都必须是单调不减的。

这样，问题就转化为：给定 $n$ 个带限制的点 $(x_i, t_i)$ ，选出一个最长的子序列，使得 $x$ 不降，且 $t-x$ 也不降。

二、解题思路

这是一个经典的二维偏序问题。

我们令 $v_i = t_i - x_i$ ，那么每个金币可以表示成 $(x_i, v_i)$ ，并且 $v_i \ge 0$ 才有意义。我们需要找最长序列满足 $x$ 不降、 $v$ 不降。

常见的做法是：先按照 $x$ 排序，如果 $x$ 相同则按照 $v$ 排序（因为 $x$ 相同时 $v$ 也必须不降）。排序后， $x$ 已经满足非降，此时问题转化为在 $v$ 序列上求最长不下降子序列（LIS）。

由于 $n \le 10^5$ ，直接用 $O(n^2)$ 的 DP 会超时。我们需要使用 $O(n \log n)$ 的经典 LIS 算法。

三、算法说明（附带代码解释）

我们维护一个数组 f[len]，表示当前所有长度为 len 的不下降子序列中，末尾元素的最小可能值。算法流程如下：

读入数据，计算 $v_i = t_i - x_i$ 。
建立索引数组 $p$ ，按照 $x$ 升序、 $v$ 升序（等价于原来的 $t$ 升序）排序。
初始化 f[0] = -∞，其余 f[i] 为一个极大值，当前最大长度 mx = 0。
按排序后的顺序遍历金币，令 v 为当前金币的 $t-x$ $t - x$ ：
- 若 v < 0，忽略（不可达）。
- 在 f[1..mx] 中二分查找最后一个 ≤ v 的位置 r。
- 那么以当前金币结尾的子序列长度可以达到 r + 1，更新 f[r+1] = v。
- 同时用 r+1 更新答案 mx。
最终 mx 即为最多收集的金币数。

二分查找细节：由于我们允许 $v$ 相等（不下降），所以要找最后一个小于等于 $v$ 的元素。参考代码中 if (v < f[mid]) r = mid - 1; else l = mid; 写法正是这样的二分，l 最终指向满足条件的最大下标。

为什么按 $x$ 相同时要按 $v$ 升序排列？如果两枚金币的 $x$ 相同，它们显然不能同时被收集，而 $v$ 不降的要求保证了先拿 $v$ 小的（即 $t$ 小的），这符合时间先后。如果排列顺序不对，可能会在同一个 $x$ 上错误地选出多枚金币。

cpp
1#include <algorithm>
2#include <cstdio>
3using namespace std;
4
5const int oo = 2e9;          // 一个较大的数，当无穷大用
6const int N = 1e5 + 5;
7
8int n;
9int x[N], t[N];              // 坐标、时间
10int p[N], f[N];              // 排序索引、LIS 辅助数组
11int mx;
12
13bool cmp(int a, int b) {
14    // 优先按 x 升序，x 相同按 t 升序（此时 t 是 v = t - x）
15    if (x[a] != x[b]) return x[a] < x[b];
16    return t[a] < t[b];
17}
18
19int main() {
20    scanf("%d", &n);
21    for (int i = 1; i <= n; i++) {
22        scanf("%d%d", &x[i], &t[i]);   // 注意输入顺序：先 x 后 t
23        t[i] -= x[i];                  // 转化为 v = t - x
24        p[i] = i;                     // 初始化索引
25        f[i] = oo;                    // f 数组初始化 INF
26    }
27    sort(p + 1, p + n + 1, cmp);      // 按 x 和 v 排序
28
29    mx = 0;                           // 记录最长 LIS 长度
30    f[0] = -oo;                       // 边界：长度 0 时末尾视为 -∞
31
32    for (int i = 1; i <= n; i++) {
33        int v = t[p[i]];              // 当前金币的 v 值
34        if (v < 0) continue;          // 不可达，跳过
35
36        int l = 0, r = mx;
37        while (l < r) {               // 二分查找最后一个 ≤ v 的 f[r]
38            int mid = (l + r) / 2 + 1;
39            if (v < f[mid])
40                r = mid - 1;
41            else
42                l = mid;
43        }
44        // 此时 r = l 为满足 f[r] ≤ v 的最大长度
45        mx = max(mx, r + 1);          // 更新最大长度
46        f[r + 1] = v;                 // 更新该长度的最小末尾元素
47    }
48
49    printf("%d\n", mx);
50    return 0;
51}

四、时间复杂度分析

排序：对 $n$ 个元素排序，时间复杂度 $O(n \log n)$ 。
LIS 计算：遍历 $n$ 个元素，每个元素进行一次二分查找，单次 $O(\log n)$ ，总复杂度 $O(n \log n)$ 。

整体时间复杂度 $O(n \log n)$ ，空间复杂度 $O(n)$ ，在 $n=10^5$ 的数据范围内可以高效运行。

五、总结

本题的关键在于将原问题中的移动条件转化为 $x$ 不降且 $t-x$ 不降 的二维偏序关系。排序后即可用经典的 LIS 算法求解。这类“最多收集多少个点”的题目，往往都可以通过分析点之间的可到达条件，转化为偏序问题来处理。

注意：代码中输入变量的顺序与常规习惯可能不同，读入时先写 x 后写 t，参赛时务必仔细看清题目要求。

题库

题库

12851.金币收集

题解大全共 1 篇