简答题
偏难
#19998
金币收集
金币收集



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include <algorithm>
#include <cstdio>
using namespace std;
const int INF = 2e9;
const int N = 100005;
int n;
int x[N], t[N];
int p[N], f[N];
int mx;
// 排序规则:先按x升序,x相同则按t升序
bool cmp(int a, int b) {
if (x[a] != x[b])
return x[a] < x[b];
return t[a] < t[b];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &x[i], &t[i]);
t[i] -= x[i]; // 转换为 t' = t - x
p[i] = i; // 下标数组,用于排序
f[i] = INF;
}
// 按x从小到大排序所有点
sort(p + 1, p + n + 1, cmp);
mx = 0;
f[0] = 0;
for (int i = 1; i <= n; ++i) {
int val = t[p[i]];
if (val < 0) continue; // 负数直接无法选取
// 二分查找最大长度r,满足 f[r] <= val
int l = 0, r = mx;
while (l < r) {
int mid = (l + r) / 2 + 1;
if (val < f[mid])
r = mid - 1;
else
l = mid;
}
// 可以拼出长度 r+1 的子序列
mx = max(mx, r + 1);
if (val < f[r + 1]) {
f[r + 1] = val;
}
}
printf("%d\n", mx);
return 0;
}</pre>
这道题暂未补解析。