#P6927. [ICPC2016 WF] Swap Space
[ICPC2016 WF] Swap Space
题目描述
You administer a large cluster of computers with hard drives that use various file system types to store data. You recently decided to unify the file systems to the same type. That is quite a challenge since all the drives are currently in use, all of them are filled with important data to the limits of their capacities, and you cannot afford to lose any of the data. Moreover, reformatting a drive to use a new file system may significantly change the drive’s capacity. To make the reformat possible, you will have to buy an extra hard drive. Obviously, you want to save money by minimizing the size of such extra storage.
You can reformat the drives in any order. Prior to reformatting a drive, you must move all data from that drive to one or more other drives, splitting the data if necessary. After a drive is reformatted, you can immediately start using it to store data from other drives. It is not necessary to put all the data on the same drives they originally started on – in fact, this might even be impossible if some of the drives have smaller capacity with the new file system. It is also allowed for some data to end up on the extra drive.
As an example, suppose you have four drives , , , and with drive capacities , , , and GB. Under the new file system, the capacities become , , , and GB, respectively. If you buy only GB of extra space, you can move the data from drive there and then reformat drive . Now you have GB free on drive , so you can move the GB from drive there and reformat drive . Finally, you move the six total gigabytes from drives and to drive , and reformat and .
输入格式
The input begins with a line containing one integer (), which is the number of drives in your cluster. Following this are lines, each describing a drive as two integers and , where is the capacity with the old file system and is the capacity with the new file system.
All capacities are given in gigabytes and satisfy . (One thousand petabytes should be enough for everyone, right?)
输出格式
Display the total extra capacity in gigabytes you must buy to reformat the drives.
题目大意
你有 个硬盘 ,现在需要对所有硬盘进行格式化。格式化后,第 个硬盘的容量会由原来的 变为 。由于容量的改变,你需要购买硬盘容量来实现数据转移。数据可以分段转移,如把大小为 的数据分别存放在两个硬盘中,一个存 一个存 。一个硬盘被格式化后可以直接使用。求购买额外容量的最小值。
4
6 6
1 7
3 5
3 5
1
4
2 2
3 3
5 1
5 10
5
提示
Time limit: 5000 ms, Memory limit: 1048576 kB.
International Collegiate Programming Contest (ACM-ICPC) World Finals 2016