02289. 驿站派件 · 林老师的题库

题目描述

小码王门口有一间快递驿站。夜里到了 $n$ 个待派件的包裹，第 $i$ 个包裹需要连续 $t_{i}$ 分钟才能派完（一旦开始就不能中断），并且必须在第 $d_{i}$ 分钟结束之前派完。

驿站第 $0$ 分钟开始上班，一次只能派一个包裹。派不完的包裹会退回收件人自取。

请问今晚最多能派完多少个包裹？

第一行一个整数 $n$ 。

接下来 $n$ 行，每行两个整数 $t_{i}$ 与 $d_{i}$ ，含义如题面所述。

一行一个整数，表示最多能派完的包裹个数。

输入

输出

说明：按第 4、2、1 个包裹的顺序派（耗时 1、2、3），完成时刻分别是 1、3、6 —— 第三个超了第 1 个包裹的截止时间 5，所以要丢掉一个。丢掉耗时 3 的那个之后，剩下三个的完成时刻是 1、3、7，都赶在各自截止时间之前。

测试点	规模与性质	分值
$1 \sim 5$	$n \leq 8$ ， $1 \leq t_{i} \leq 10$ ， $1 \leq d_{i} \leq 25$	$25$
$6 \sim 8$	所有 $t_{i} = 1$ ， $n \leq 2 \times 1 0^{5}$	$15$
$9 \sim 12$	所有 $d_{i}$ 相同， $n \leq 2 \times 1 0^{5}$	$20$
$13 \sim 20$	$1 \leq n \leq 2 \times 1 0^{5}$ ， $1 \leq t_{i} \leq 1 0^{9} + 1$ ， $1 \leq d_{i} \leq 1 0^{15}$	$40$

全部数据保证：第 $13 \sim 20$ 个测试点里 $t_{i} \geq 2$ ，且所有测试点的答案都不是 $0$ 也不是 $n$ （即总有事干、也总有活干不完）。