Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom6月前

12/17
16:47
贪心

[bzoj 4619] [Wf2016]Swap Space

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

你有许多电脑,它们的硬盘用不同的文件系统储存数据。你想要通过格式化来统一文件系统。格式化硬盘可能使它的容量发生变化。为了格式化,你需要买额外的硬盘。当然,你想要买容量最小的额外储存设备以便省钱。你可以按任意顺序格式化硬盘。格式化之前,你要把该硬盘上所有数据移到一个或更多的其他硬盘上(可以分割数据)。格式化后,该硬盘可以立刻开始使用。你没有必要把数据放到它原来所在的硬盘上。数据也可以被放到你额外买的硬盘上。举个例子,假设你有4个硬盘A、B、C、D,容量分别为6、1、3、3(GB)。新的文件系统下,它们的容量变为6、7、5、5(GB)。如果你只买1GB额外空间,你可以把B硬盘的数据放过去然后格式化硬盘B。现在你的B硬盘有7GB容量了,那么你就可以把A的数据放过去然后格式化A,最后把C、D的数据放到A上,再格式化C和D。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行一个数n(1≤n≤1,000,000),表示你的硬盘数。接下来n行,每行两个数a和b,分别表示该硬盘的原容量和新文件系统下的容量。所有容量都以GB为单位,且1≤a,b≤1,000,000,000。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出如果要格式化所有硬盘,你最少需要购买多少额外空间(GB)。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

10
11 82
98 12
78 53
15 10
41 2
81 58
53 42
30 41
25 39
20 54

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

61

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

同bzoj3709贪心,先把b>a的按照a升序排一边,然后b<=a的b降序排一遍

 

[bzoj 4619] [Wf2016]Swap Space