Toggle navigation
算苗科技
题目
状态
排名
竞赛&作业
开放课演练
登录
注册
3824木板 (farme)
3824 木板 (farme)
题目描述
有n个单位宽度的木板,每块木板的长度是Li.每块木板中间都有一个空槽,空槽必须在P
i
处的钉子上,如图10.4-1所示。
现在,要选出尽可能多的木板并且将他们安排在一个直线上,使得没有两块木板相交(一个
包含另外一个当然也是禁止的,不过边界相碰是允许的),空槽两端忽略不计,钉子也非常细,
以安置在木板的边界,就是说木板的左端点的可能位置是P
i
-L
i
至P
i
.没有两颗钉子在同一个
位置。
输入格式:
第1行1个正整数n,代表木板的数量(1<n< 100000).
接下来的每一行包含两个正整数Li和P
i
(1<=L
i
, P
i
<=10000000)代表第i块木板的长度,以及相关的钉子的位置。
输出格式:
输出一行一个整数,代表可以选择的最多的木板。
输入样例
复制
7 5 9 2 17 6 10 3 11 2 16 4 13 5 6
输出样例
复制
5
说明
提交
0
0
通过
提交
时空限制
1000ms/64mb
题目来源
评测方式
在线评测
题目类型
queue
难 度
提交
题解
提交状态