2040_磁带最优存储问题

设有n 个程序 { 1, 2, …, n } 要存放在长度为 L 的磁带上。程序i存放在磁带上的长度是l_i ，1 ≤ i ≤ n。这n个程序的读取概率分别是 p₁ , p₂ , ... , p_n ，且 。

如果将这n个程序按i₁ , i₂ , ... ,i_n 的次序存放，则读取程序 i_r 所需的时间 。  这n个程序的平均读取时间为 。

磁带最优存储问题要求确定这n个程序在磁带上的一个存储次序，使平均读取时间达到最小。

对于给定的n个程序存放在磁带上的长度和读取概率，试设计一个解此问题的算法，计算n个程序的最优存储方案，并分析算法的正确性和计算复杂性。

输入数据。第一行是正整数n，表示文件个数。接下来的n行中，每行有2个正整数a 和b，分别表示程序存放在磁带上的长度和读取概率。实际上第k个程序的读取概率 。对所有输入均假定c=1。

输出最小平均读取时间。

把计算结果值，从左到右共需输出6个数字，其余舍弃。

5
71 872
46 452
9 265
73 120
35 85

85.6193