磁带最优存储问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是Li, 
1<= i<= n。这n 个程序的读取概率分别是p1,p2,...,pn,且pi+p2+...+pn = 1。如果将这n 个程序按 
i1,i2,....,in 的次序存放,则读取程序ir 所需的时间tr=c*(Pi1*Li2+Pi2*Li2+...+Pir*Lir)。这n 个程序的平均读取 
时间为t1+t2+...+tn。 
磁带最优存储问题要求确定这n 个程序在磁带上的一个存储次序,使平均读取时间达到 
最小。试设计一个解此问题的算法,并分析算法的正确性和计算复杂性。 
编程任务: 
对于给定的n个程序存放在磁带上的长度和读取概率,编程计算n个程序的最优存储方 
案。

Input

由文件input.txt给出输入数据。第一行是正整数n,表示文件个数。接下来的n行中, 
每行有2 个正整数a 和b,分别表示程序存放在磁带上的长度和读取概率。实际上第k个程 
序的读取概率ak/(a1+a2+...+an)。对所有输入均假定c=1。

Output

输出一个实数,保留1位小数,表示计算出的最小平均读取时间。

Sample Input

5
71 872
46 452
9 265
73 120
35 85

Sample Output

85.6

Hint

 

Source