题目描述
小 A 正在游玩收集金币的游戏。具体来说，在数轴上将会出现 n 枚金币，其中第 i 枚（1≤i≤n）金币将会在时刻 ti 出现在数轴上坐标为 xi 的位置。小 A 必须在时刻 ti 恰好位于坐标 xi，才可以获得第 i 枚金币。
游戏开始时为时刻 0，此时小 A 的坐标为 0。正常来说，小 A 可以按游戏机的按键在数轴上左右移动，但不幸的是游戏机的左方向键失灵了。小 A 每个时刻只能选择保持不动，或是向右移动一个单位。换言之，如果小 A 在时刻 t 的坐标为 x，那么他在时刻 t+1 的坐标只能是 x 或是 x+1 二者之一，分别对应保持不动和向右移动。
小 A 想知道他最多能收集多少枚金币。你能帮他收集最多的金币吗？
输入格式
第一行，一个正整数 n，表示金币的数量。
接下来 n 行，每行两个正整数 xi,ti，分别表示金币出现的坐标与时刻。
输出格式
输出一行，一个整数，表示小 A 最多能收集的金币数量。
输入输出样例
输入 #1
3 1 6 3 7 2 4
输出 #1
2
输入 #2
4 1 1 2 2 1 3 2 4
输出 #2
3
说明/提示
对于 40% 的测试点，保证 1≤n≤8。
对于另外 30% 的测试点，保证 1≤n≤100，1≤xi≤100，1≤ti≤100。
对于所有测试点，保证 1≤n≤105，1≤xi≤109，1≤ti≤109。
题目分析
问题核心：小A只能向右移动或静止，求最多能收集的金币数（需在时刻ti 恰好位于xi ）。
约束条件：
若收集金币i和j（i在j之前），需满足：
1.xi≤xj（只能右移，位置不下降）；
2.tj−ti≥xj−xi（时间差足够移动距离）。
化简条件2得：tj−xj≥ti−xi。
转化与解法：
对金币按xi排序后，问题等价于求ti−xi的「最长非递减子序列」长度（动态规划+二分优化）
代码注释
#include <algorithm>
#include <cstdio>
#include <climits>
using namespace std;
const int N = 1e5 + 5; // 最大金币数
int n;
int x[N], t[N]; // 金币i：位置x[i]，时间t[i]
int p[N]; // 排序用的索引数组
long long f[N]; // 用long long避免溢出，f[k]表示长度为k的序列末尾的t-x最小值
// 排序规则：先按x升序，x相同时按(t-x)升序；x不同时，确保t-x非递减
bool cmp(int a, int b) {
if (x[a] != x[b]) return x[a] < x[b];
return (t[a] - x[a]) < (t[b] - x[b]);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &x[i], &t[i]);
p[i] = i;
}
// 初始化f数组为无穷大（表示初始时这些长度的序列不存在）
fill(f, f + N, LLONG_MAX);
f[0] = 0; // 长度为0的序列：时刻0，位置0，t-x=0-0=0
int mx = 0; // 最长序列长度
// 按x升序排序，x相同则按(t-x)升序
sort(p + 1, p + n + 1, cmp);
for (int i = 1; i <= n; i++) {
int idx = p[i];
long long xi = x[idx];
long long ti = t[idx];
long long v = ti - xi; // 核心判断值：必须>=0且非递减
// 基础条件：t[i] >= x[i]（否则无法到达）
if (v < 0) continue;
// 二分查找：找到最大的k，使得f[k] <= v
int l = 0, r = mx;
while (l < r) {
int mid = (l + r + 1) / 2; // 向上取整避免死循环
if (f[mid] <= v) { // 原代码此处符号写反，修正为<=
l = mid;
} else {
r = mid - 1;
}
}
// 尝试更新长度为l+1的序列的末尾值
if (v < f[l + 1]) {
f[l + 1] = v;
}
// 更新最长序列长度
if (l + 1 > mx) {
mx = l + 1;
}
}
printf("%d\n", mx);
return 0;
}
复杂度分析
时间复杂度：O(nlogn)，排序耗时O(nlogn)，二分查找总耗时O(nlogn)，适用于n≤1e5的数据范围。
空间复杂度：O(n)，用于存储金币信息和动态规划数组。