2041_磁盘文件最优存储问题

设磁盘上有n个文件f₁ , f₂ , ... , f_n ，每个文件占磁盘上1个磁道。这n个文件的检索概率分别是 p₁ , p₂ , ... , p_n ,且 。磁头从当前磁道移到被检信息磁道所需的时间可用这2个磁道之间的径向距离来度量。如果文件 f_i 存放在第i道上，1 ≤ i ≤ n，则检索这n个文件的期望时间是。其中d(i,j)是第i道与第j道之间的径向距离|i-j|。

磁盘文件的最优存储问题要求确定这n个文件在磁盘上的存储位置，使期望检索时间达到最小。

对于给定的文件检索概率，试设计一个解此问题的算法，计算磁盘文件的最优存储方案，并分析算法的正确性与计算复杂性。

输入的第一行是正整数n，表示文件个数。第2行有n个正整数a_i，表示文件的检索概率。实际上第k个文件的检索概率应为

输出最小期望检索时间。把计算结果值，从左到右共需输出6个数字，其余舍弃

5
33 55 22 11 9

0.547396