。其中 d(i, j) 是第i 道与第 j 道之间的径向距离|i-j|。磁盘文件的最优存储问题要求确定这 n 个文件在磁盘上的存储位置， 使期望检索时间达到最小。
算法设计：
对于给定的文件检索概率， 试设计一个解此问题的算法， 计算磁盘文件的最优存储方案，并分析算法的正确性与计算复杂性。
1383: 算法实现题 4-4 磁盘文件最优存储问题（习题 4-7）
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $1$ | 正确数量 | $2$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 | 贪心 |
Description
设磁盘上有 n 个文件f1, f 2 ,..., f n ，每个文件占磁盘上 1 个磁道。这 n 个文件的检索概率分别是p1, p2 ,..., pn ,且p1+p2+...+pn=1。磁头从当前磁道移到被检信息磁道所需的时间可用这2 个磁道之间的径向距离来度量。如果文件 f i 存放在第i 道上,1 <= i <= n ，则检索这 n 个文件的期望时间是 。其中 d(i, j) 是第i 道与第 j 道之间的径向距离|i-j|。磁盘文件的最优存储问题要求确定这 n 个文件在磁盘上的存储位置， 使期望检索时间达
到最小。
算法设计：
对于给定的文件检索概率， 试设计一个解此问题的算法， 计算磁盘文件的最优存储方案，并分析算法的正确性与计算复杂性。
。其中 d(i, j) 是第i 道与第 j 道之间的径向距离|i-j|。磁盘文件的最优存储问题要求确定这 n 个文件在磁盘上的存储位置， 使期望检索时间达到最小。
算法设计：
对于给定的文件检索概率， 试设计一个解此问题的算法， 计算磁盘文件的最优存储方案，并分析算法的正确性与计算复杂性。
Input
输入第一行是正整数 n，表示文件个数。第 2 行有 n 个正整数 ai，表示文件的检索概率。实际上第 k 个文件的检索概率应为
Output
输出最小期望检索时间
Sample Input复制
5
33 55 22 11 9
Sample Output复制
0.547396
推荐代码 查看1383 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$106 $ms] | 大喵-sama | 900311 | 2022-10-11 16:23:59 |
| 内存最少[$2088 $KB] | 李猪不是猪 | 668713 | 2020-11-27 14:30:25 |
| 第一AC | 李猪不是猪 | 668713 | 2020-11-27 14:30:25 |
| 第一挑战 | 李猪不是猪 | 668713 | 2020-11-27 14:30:25 |
赛题来源/所属竞赛 NA 算法导论(第三版)中文完整高清版
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|