TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1404
  • 题目
  • P1404【分类练习3.贪心】线性存储问题
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    磁带等存储介质存储信息时基本上都是一种线性存储的方式,线性存储方式虽然简单,但查询检索时往往要经过一些其它信息,不象磁盘等存储介质在目录区找到后可直接定位到某一区城,因此线性存储总有它的局限性。但是由于磁带等线性存储有简单、保存时间相对较长等优点,现在仍然在使用。

    如果有n段信息资料要线性存储在某种存储介质上,它们的长度分别是L1,L2,…,Ln,存储介质能够保存下所有这些信息,假设它们的使用(查询检索)的频率分别是F1,F2,…,Fn,要如何存储这些信息资料才能使平均检索时间最短。

    你的任务就是编程安排一种平均检索时间最短的方案。


    输入格式

    第一行是一个正整数n(n<10000),

    接下来是n行数据,
    每行两个整数分别是第1段信息的长度(1到10000之间)和使用的频率(万分比,在0到9000之间),总的频率之和为10000。

    所输入数据均不要判错

    输出格式

    依次存储信息段的编号。每个数据之间用一个空格隔开。
    (在输出数据中,可能存在着多个相同的最佳方案,在排序时请务必保证数据的稳定性,否则结果可能不一样!)

    样例输入

    5
    10 4000
    20 1000
    30 1000
    35 1500
    12 2500

    样例输出

    4 1 3 5 2

    提示

    输出字典序最小的方案