‹ 上一题 下一题 ›

s09177. 最短作业优先·单机 未做

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

题目描述

一台打印机从时刻 开始工作,同一时刻只能打印一份文档,打印一旦开始不可中断。第 份文档在时刻 到达,需要连续打印 分钟。

打印顺序遵循最短作业优先:每当打印机空闲时,在所有已到达且未打印的文档中,选 最小的一份开始打印;若有多份 相同,选 最小的;仍相同则选输入顺序靠前的。若打印机空闲时还没有文档到达,时间直接跳到下一份文档的到达时刻。

第 份文档的等待时长定义为它的开始打印时刻减去 。请按上述规程模拟,输出全部文档等待时长之和。

输入格式

第一行一个整数 。

接下来 行,第 行两个整数 。

输出格式

一行一个整数,表示全部文档等待时长之和。

样例 1

样例

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

时刻 只有一份文档可打,打印至 ;此时三份文档已到达,选时长 的(等待 ),再选时长 的(等待 ),最后选时长 的(等待 ),总等待 。

样例 2

第一份打印到 ,打印机空闲且下一批文档 才到达,时间跳到 ;先打时长 的,另一份从 等起,等待 。

数据范围

;;。答案可能超过 位整数的表示范围,数据保证答案在 位整数范围内。

输入
输出

            
答案