题目描述
设磁盘上有n 个文件f 1, f2 ,…… , fn ，每个文件占磁盘上1 个磁道。这n 个文件的检索概率分别是 p1 , p2 ,……, pn，且
。
磁头从当前磁道移到被检信息磁道所需的时间可用这2 个磁道之间的径向距离来度量。如果文件fi 存放在第i道上,1≤ i ≤ n，则检索这n 个文件的期望时间是
。
其中d(i, j)是第i道与第j 道之间的径向距离|i-j|。
磁盘文件的最优存储问题要求确定这n 个文件在磁盘上的存储位置，使期望检索时间达到最小。
对于给定的文件检索概率，试设计一个解此问题的算法，计算磁盘文件的最优存储方案，并分析算法的正确性与计算复杂性。
输入
输入数据的第一行是正整数n（n≤20000），表示文件个数。第2 行有n个正整数ai，表示文件的检索概率。实际上第k个文件的检索概率应为
输出
输出一个实数，表示计算出的最小期望检索时间。
用%g输出。
样例输入
5
33 55 22 11 9
样例输出
0.5
参考代码
暂无
解析
暂无
