在 线 评 测 系 统
Toggle navigation
ZUEBOJ
常见问答
问题
来源/分类
状态
排名
竞赛
(2)
考试与作业
(2)
Login
Language
中文
ئۇيغۇرچە
English
فارسی
ไทย
한국어
问题2444--印刷机
2444: 印刷机
[命题人 :
]
时间限制 :
12
sec
内存限制 :
128 MB
提交
解决: 1
提交量: 3
统计
题目描述
有 $N$ 个标有 $1$ 至 $N$ 的产品在传送带上流动。传送带上有一台
晨光
打印机,产品 $i$ 在 $T_i$ 微秒后进入打印机的打印范围,并在 $D_i$ 微秒后离开打印机(也就是说这个产品需要占用打印机
$D_i$ 微秒
)。
晨光打印机可以即时打印打印机范围内的一个产品(尤其是在产品进入或离开打印机范围的瞬间)。但打印一次后,需要充电 $1$ 微秒才能再次打印。如果产品和打印机打印时间选择最优,打印机最多可以打印多少产品?
输入
第一行一个整数N表示共有N个产品
接下来N行,每行两个整数分别表示
产品 $i$ 在 $T_i$ 微秒后进入打印机的打印范围,并在 $D_i$ 微秒后离开打印机
$ 1\leq\ N\ \leq\ 2\times\ 10^5 $
$ 1\leq\ T_i,D_i\ \leq\ 10^{18} $
所有输入值均为整数
输出
输出一个整数,表示打印机最多可以打印多少产品
样例输入
Copy
5 1 1 1 1 2 1 1 2 1 4
样例输出
Copy
4
提示
样例输入2:
10
4 1
1 2
1 4
3 2
5 1
5 1
4 1
2 1
4 1
2 4
样例输出2:
6
样例输入3:
2
1 1
1000000000000000000 1000000000000000000
样例输出3:
2
来源/分类
大数据与人工智能学院2023级ACM集训队选拔赛(2)