若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1740: 磁盘文件最优存储问题

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,064

题目描述

设磁盘上有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

参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

电子邮件地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Dreams孤独患者 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist