A23805. 金币收集
填空题
困难
知识点
题目描述
金币收集
题目描述
小 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 。
参考答案
#include <algorithm>
#include <cstdio>
using namespace std;
const int oo = 2e9;
const int N = 1e5 + 5;
int n;
int x[N], t[N];
int p[N], f[N];
int mx;
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];
p[i] = i;
f[i] = oo;
}
sort(p + 1, p + n + 1, cmp);
mx = 0;
f[0] = 0;
for (int i = 1; i <= n; i++) {
int l = 0, r = mx;
int v = t[p[i]];
if (v < 0) continue;
while (l < r) {
int mid = (l + r) / 2 + 1;
if (v < f[mid])
r = mid - 1;
else
l = mid;
}
mx = max(mx, r + 1);
f[r + 1] = v;
}
printf("%d\n", mx);
return 0;
}
上一题
下一题