网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
线性存储问题
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | linstorage.in | 输出文件 | linstorage.out |
【问题描述】
磁带等存储介质存储信息时基本上都是一种线性存储的方式,线性存储方式虽然简单,但查询检索时往往要经过一些其它信息,不象磁盘等存储介质在目录区找到后可直接定位到某一区城,因此线性存储总有它的局限性。但是由于磁带等线性存储有简单、保存时间相对较长等优点,现在仍然在使用。
如果有n段信息资料要线性存储在某种存储介质上,它们的长度分别是L1,L2,…,Ln,存储介质能够保存下所有这些信息,假设它们的使用(查询检索)的频率分别是F1,F2,…,Fn,要如何存储这些信息资料才能使平均检索时间最短。
你的任务就是编程安排一种平均检索时间最短的方案。(字典序输出)
【输入】
第一行是一个正整数n(n<10000),接下来是n行数据,每行两个整数分别是第1段信息的长度(1到10000之间)和使用的频率(万分比,在0到9000之间),总的频率之和为10000。
所输入数据均不要判错。
【输出】
依次存储信息段的编号。每个数据之间用一个空格隔开。
【样例】
storage.in storage.out
5 4 1 3 5 2
10 4000
20 1000
30 1000
35 1500
12 2500