冲刺NOIP2011长乐一中day2.doc

【注意事项】:请自行完成题目,切勿讨论。题1内存管理【问题描述】Windows的内存管理系统是十分复杂的,我们要求你编写一个程序,来模拟内存管理操作。计算机的内存被分割成30000个相同大小的连续区域,每个区域被称作一个内存块(Block),这些内存块被依次编号为1,2,3,...,29998,29999,30000。内存管理的基本单位是块,即某个应用程序申请或访问的内存必须是块的整数倍。当某应用程序申请或访问内存时,该应用程序会向Windows发送一条消息(Message):1、<Time>+表示应用程序在第Time秒向Windows发送一条申请内存的消息;2、<Time>.<Label>表示应用程序在第Time秒向Windows发送一条访问第Label块内存的消息。其中,<Time>和<Label>会在真正的消息中被替换为相应数字。程序开始时,所有内存块均处于空闲状态。对于申请内存的消息,Windows系统会将当前空闲内存块中编号最小的那一块分配给相应的应用程序,并且相应内存块转变为被占用状态。对于访问内存的消息,若当前内存块处于被占用状态,则Windows系统会反馈一个“+”表示该内存块可以被访问,否则反馈一个“-”表示程序无法访问该内存块。对于任何被占用的内存块,若在600秒内无任何操作,则该内存块会被系统释放掉,重新变为空闲状态。【输入格式】输入文件包含若干行,每行描述一条消息,消息共有两种:1、<Time>+2、<Time>.<Label>消息含义见问题描述。+前有一个空格,.的前后都有一个空格,其他地方无多于空格。保证Time按照非递减顺序出现,对于在同一时刻发出的消息,按照输入顺序处理。【输出格式】对于每条申请内存的消息,输出Windows分配给该应用程序的内存块编号。对于每条访问内存的消息,输出“+”或“-”表示该内存块是否可以被成功访问。【输入输出样例】+1+1++602+++--+-13-【样例说明】对于前3条申请内存的消息,Windows系统依次将1、2、3号内存块分配给应用程序,若在接下来600秒内没有对这些内存块进行任何操作,这些内存块将在第601秒时被系统释放掉;对于接下来3条访问内存的消息,2号和3号内存块在占用,返回“+”,同时它们的释放时间被推迟到第602秒。30000号内存块未被占用,于是返回“-”;再接下来3条访问内存的消息,由于在第601秒时1号内存块被释放,在第602秒时2号和3号内存块被释放,所以依次返回“-”、“+”和“-”,同时2号内存块的释放时间被推迟到第1201秒;下面2条申请内存的消息,由于目前1号和3号是空闲内存块,2号在被占用,所以Windows分别将1号和3号内存块分配给应用程序,并且1号和3号内存块的释放时间为第1202秒。最后一条访问内存的消息,由于2号内存块已在第1201秒时被释放掉,因此返回“-”。【数据规模和约定】对于20%的