对于先捡到的金币 A 和后捡到的金币 B,必须满足:
TB−TA>∣XB−XA∣绝对值不等式可以拆成:
多多在玩一个横版视角的接金币游戏:控制的角色只能向右移动,最大移动速度为 1 个单位距离/秒;地图上总共会出现 N 枚金币,第 i 枚金币会在 Ti 秒时,准确掉落在坐标 Xi 的位置,如果没被接住就会瞬间消失。
为了接住金币,你必须在 Ti 秒时出现在 Xi 坐标。此外,由于角色捡金币需要短暂的硬直时间,如果你接住了金币 A,想要再去接金币 B,两次的时间间隔必须严格大于你在两地之间移动所需的时间,即满足公式:
TB−TA>∣XB−XA∣假设游戏开始前,你可以在任意位置等待。请问你整场游戏最多能接住多少枚金币?
注意:如果同一时刻坐标 X 有多枚金币同时掉落,最多只可以接到一个。
第一行包含一个整数 N(1≤N≤105),表示金币的数量。
接下来 N 行,每行两个整数 Ti 和 Xi,1≤Ti≤109,−109≤Xi≤109,分别表示金币出现时刻和坐标。
输出一个整数,表示你最多能收集到的金币数量。
输入
5
1 2
5 5
2 3
7 4
6 8
输出
3
说明
最优接金币路径之一为:提取【金币1】→【金币2】→【金币4】,总共 3 枚。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册