‹ 上一题 下一题 ›

s09148. 打印店的口径 未做

1000 ms 256 MB 测试点 10 通过率 17% S-06·贪心进阶与反悔贪心优先队列贪心

题目描述

文印店有一台打印机,从时刻 开始工作。今有 个打印任务,任务 在时刻 到达,需要连续打印 秒。打印机同一时刻只能打印一个任务,打印一旦开始不可中断。

关于先打印哪个任务,同学们有两种主张:先来先做,或最短优先。本题统一采用最短优先口径:每当打印机空闲时,在所有已到达且未完成的任务中,选择所需时间 最小的一个;若这样的任务有多个,选择输入序号最小的一个。打印机空闲且没有已到达的任务时,时间直接跳到下一个任务的到达时刻。

一个任务的等待时长 = 它的开始打印时刻 − 它的到达时刻。求按最短优先口径执行时,全部任务的总等待时长。

输入格式

第一行一个整数 。

接下来 行,第 行两个整数 ,含义如上。

输出格式

一行一个整数:总等待时长。

样例 1

样例

输入
4
0 7
2 4
3 1
6 2
输出
14

时刻 只有任务 ,先做任务 ( 到 );时刻 时任务 都已到达,最短的是任务 ( 到 );再是任务 ( 到 );最后任务 ( 到 )。等待 。

样例 2

先做任务 (最短,序号平局取小),再任务 ,最后任务 ;等待 。若按先来先做口径,答案为 ——两种口径在这里给出不同结果。

数据范围

;;。答案可能超过 位整数范围。

输入
输出

            
答案