若是凉夜已成梦

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


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1739: 磁带最优存储问题

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

题目描述

设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li ,1≤ i ≤ n。这n 个程序的读取概率分别是 p1 , p2 ,…… , pn ,且

如果将这n 个程序按 i1 ,i2 ,…… ,in 的次序存放,则读取程序 ir 所需的时间
。
这n 个程序的平均读取时间为
。
磁带最优存储问题要求确定这n 个程序在磁带上的一个存储次序,使平均读取时间达到最小。
对于给定的n 个程序存放在磁带上的长度和读取概率,试设计一个解此问题的算法,计算n 个程序的最优存储方案,并分析算法的正确性和计算复杂性。

输入

输入数据的第一行是正整数n(n≤1000),表示文件个数。接下来的n行中,每行有2 个正整数a 和b,分别表示程序存放在磁带上的长度和读取概率。实际上第k个程序的读取概率
 。
对所有输入均假定c=1。

输出

输出一个实数,保留1位小数,表示计算出的最小平均读取时间。

样例输入

5
71 872
46 452
9 265
73 120
35 85

样例输出

85.6

参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

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

*
*


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

若是凉夜已成梦

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

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

友情链接

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