Preparing NOJ

程序最优存储问题

1000ms 65536K

Description:

设有n 个程序{1,2,, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是li 1in。这n 个程序的读取概率分别是n p1 , p 2,…. ,Pn ,Pi=1。如果将这n 个程序按i1 , i 2,…. ,in 的次序存放,则读取程序ir所需的时间t r=c*Piklik。这n 个程序的平均读取时间为r

磁带最优存储问题要求确定这n 个程序在磁带上的一个存储序,使平均读取时间达到最小。试设计一个解此问题的算法,并分析算法的正确性和计算复杂性。

对于给定的n个程序存放在磁带上的长度和读取概率,编程计算n个程序的最优存储方案。

Input:

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

Output:

将编程计算出的最小平均读取时间输出。

Sample Input:

5
71 872
46 452
9 265
73 120
35 85

Sample Output:

85.6193

Note:

undefined

本题由旧版NOJ导入,来源:NUAA

Info

NOJ

Provider NOJ

Code NOJ1251

Tags

Submitted 36

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet