题目描述
设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li ，1≤ i ≤ n。这n 个程序的读取概率分别是 p1 , p2 ,…… , pn ,且
如果将这n 个程序按 i1 ,i2 ,…… ,in 的次序存放，则读取程序 ir 所需的时间
。
这n 个程序的平均读取时间为
。
磁带最优存储问题要求确定这n 个程序在磁带上的一个存储次序，使平均读取时间达到最小。
对于给定的n 个程序存放在磁带上的长度和读取概率，试设计一个解此问题的算法，计算n 个程序的最优存储方案，并分析算法的正确性和计算复杂性。
输入
输入数据的第一行是正整数n（n≤1000），表示文件个数。接下来的n行中，每行有2 个正整数a 和b，分别表示程序存放在磁带上的长度和读取概率。实际上第k个程序的读取概率
。
对所有输入均假定c=1。
输出
输出一个实数，保留1位小数，表示计算出的最小平均读取时间。
样例输入
5
71 872
46 452
9 265
73 120
35 85
样例输出
85.6
参考代码
暂无
解析
暂无
