7117: BZOJ3117：[Noi1999]内存分配
Memory Limit：128 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
内存是计算机重要的资源之一，程序运行的过程中必须对内存进行分配。
经典的内存分配过程是这样进行的：
1. 内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从0开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址i开始的s个连续的内存单元称为首地址为i长度为s的地址片。
2. 运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻T，需要内存单元数M及运行时间P。在运行时间P内（即T时刻开始，T+P时刻结束），这M个被占用的内存单元不能再被其他进程使用。
3、假设在T时刻有一个进程申请M个单元，且运行时间为P，则：
1. 若T时刻内存中存在长度为M的空闲地址片，则系统将这M个空闲单元分配给该进程。若存在多个长度为M个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。
2. 如果T时刻不存在长度为M的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为M的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。注意，在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其它进程不能先于队头进程被处理。
现在给出一系列描述进程的数据，请编写一程序模拟系统分配内存的过程。
经典的内存分配过程是这样进行的：
1. 内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从0开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址i开始的s个连续的内存单元称为首地址为i长度为s的地址片。
2. 运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻T，需要内存单元数M及运行时间P。在运行时间P内（即T时刻开始，T+P时刻结束），这M个被占用的内存单元不能再被其他进程使用。
3、假设在T时刻有一个进程申请M个单元，且运行时间为P，则：
1. 若T时刻内存中存在长度为M的空闲地址片，则系统将这M个空闲单元分配给该进程。若存在多个长度为M个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。
2. 如果T时刻不存在长度为M的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为M的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。注意，在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其它进程不能先于队头进程被处理。
现在给出一系列描述进程的数据，请编写一程序模拟系统分配内存的过程。
输入格式
第一行是一个数N，表示总内存单元数（即地址范围从0到N-1）。从第二行开始每行描述一个进程的三个整数T、M、P（M <= N）。最后一行用三个0表示结束。
数据已按T从小到大排序。
输入文件最多10000行，且所有数据都小于109。
输入文件中同一行相邻两项之间用一个或多个空格隔开。
数据已按T从小到大排序。
输入文件最多10000行，且所有数据都小于109。
输入文件中同一行相邻两项之间用一个或多个空格隔开。
输出格式
包括2行。
第一行是全部进程都运行完毕的时刻。
第二行是被放入过等待队列的进程总数。
第一行是全部进程都运行完毕的时刻。
第二行是被放入过等待队列的进程总数。
样例输入
10 1 3 10 2 4 3 3 4 4 4 1 4 5 3 4 0 0 0
样例输出
12 2
提示
| 时 刻 T | 内存占用情况 | 进程事件 | |||||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 进程A申请空间（M=3, P=10）<成功> | |||
| 1 | A | ||||||||||||
| 2 | A | B | 进程B申请空间（M=4, P=3）<成功> | ||||||||||
| 3 | A | B | 进程C申请空间（M=4, P=4）<失败进入等待队列> | ||||||||||
| 4 | A | B | D | 进程D申请空间（M=1, P=4）<成功> | |||||||||
| 5 | A | C | D | 进程B结束，释放空间 进程C从等待队列取出，分配空间 进程E申请空间（M=3, P=4）<失败进入等待队列> | |||||||||
| 6 | A | C | D | ||||||||||
| 7 | A | C | D | ||||||||||
| 8 | A | C | E | 进程D结束，释放空间 进程E从等待队列取出，分配空间 | |||||||||
| 9 | A | E | 进程C结束，释放空间 | ||||||||||
| 10 | A | E | |||||||||||
| 11 | E | 进程A结束，释放空间 | |||||||||||
| 12 | 进程E结束，释放空间 | ||||||||||||
题目来源
没有写明来源