F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 1359. -- [Baltic2009]Candy

1359: [Baltic2009]Candy

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 154  Solved: 12
[Submit][Status][Discuss]

Description

给定N个数对(S_i,T_i),表示时刻S_i时在位置T_i处出现一粒糖果。有一些机器人可供使用,每个机器人可花费一
单位时间向相邻位置移动。要求用最少的机器人接到全部糖果。时刻0时机器人位置可自行安排。
1≤N≤100000, 
0≤S_i,T_i≤10^9。

Input

 第一行包含一个整数 n,表示该轮生产所产生的糖果数量。
接下来的 n 行中,第 i 行包含两个整数 s_i 和 t_i,表示第 i 个糖果的产生位置和时间。

Output

Sample Input

5
1 1
2 3
1 5
3 4
2 6

Sample Output

2
样例解释:
在时刻1的时候,有两个糖果在不同的位置掉下,因此需要两个机器人分别赶到位置1和位置5
在时刻2的时候,也有两个糖果在不同的位置掉下,因此需要两个机器人分别赶到位置3和位置6
在时刻3的时候,只有一个糖果掉下,因此需要一个机器人赶到位置4
所以对于5颗糖果需要的机器人编号分别为1 1 2 1 2

HINT

Source

[Submit][Status][Discuss]

HOME Back