Preparing NOJ

磁盘文件最优存储问题

1000ms 65536K

Description:

设磁盘上有n 个文件f1f2, …, fn. ,每个文件占磁盘上1 个磁道。这n 个文件的检索概率分别是p1, p2, pn,=1。磁头从当前磁道移到被检信息磁道所需的时间可用这2 个磁道之间的径向距离来度量。如果文件fi存放在第i道上,1in,则检索这n 个文件的期望时间是 。其中d(i, j)是第i道与第j 道之间的径向距离|i-j|

磁盘文件的最优存储问题要求确定这n 个文件在磁盘上的存储位置,使期望检索时间达到最小。试设计一个解此问题的算法,并分析算法的正确性与计算复杂性。

对于给定的文件检索概率,编程计算磁盘文件的最优存储方案。

Input:

由文件input.txt给出输入数据。第一行是正整数n,表示文件个数。第2 行有n个正整数ai,表示文件的检索概率。实际上第k个文件的检索概率应为

Output:

将编程计算出的最小期望检索时间输出。

Sample Input:

5
33 55 22 11 9

Sample Output:

0.547396

Note:

undefined

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

Info

NOJ

Provider NOJ

Code NOJ1252

Tags

Submitted 38

Passed 10

AC Rate 26.32%

Date 04/20/2019 10:03:10

Related

Nothing Yet