磁带最优存储问题

发布时间: 2017年6月19日 00:24   时间限制: 1000ms   内存限制: 128M

设有n个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是li 1 £ i £ n。这n 个程序的读取概率分别是p1p2pn, [图片]

 

 

如果将这n个程序按i1i2in的次序存放,则读取程序ir所需的时间tr =c*[图片]。这n 个程序的平均读取时间为[图片]

 

 

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

有多组测试数据。每组的第一行是正整数n,表示文件个数。接下来的n行中,每行有2个正整数ab,分别表示程序存放在磁带上的长度和读取概率,(n£8000ab£10000)。实际上第k个程序的读取概率 [图片]

对所有输入均假定c=1

对每组测试数据,一行输出最小平均读取时间,四舍五入保留4位小数。

复制
5
71 872
46 452
9 265
73 120
35 85
7
7 368
68 27
13 805
34 755
72 957
6 138
67 273
85.6193
74.2308
1755

old_judge

old_judge_None