内存分配模拟问题

题目描述

内存是计算机重要的资源之一，程序运行的过程中必须对内存进行分配。

经典的内存分配过程是这样进行的：

1. 内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从 0 开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址 $i$ 开始的 $s$ 个连续的内存单元称为首地址为 $i$ 长度为 $s$ 的地址片。

2. 运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻 $T$，需要内存单元数 $M$ 及运行时间 $P$。在运行时间 $P$ 内（即 $T$ 时刻开始，$T+P$ 时刻结束），这 $M$ 个被占用的内存单元不能再被其他进程使用。

3. 假设在 $T$ 时刻有一个进程申请 $M$ 个单元，且运行时间为 $P$，则：

   • 若 $T$ 时刻内存中存在长度为 $M$ 的空闲地址片，则系统将这 $M$ 个空闲单元分配给该进程。若存在多个长度为 $M$ 个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。
   • 如果 $T$ 时刻不存在长度为 $M$ 的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为 $M$ 的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。注意，在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其它进程不能先于队头进程被处理。

现在给出一系列描述进程的数据，请编写一程序模拟系统分配内存的过程。

输入格式

第一行是一个数 $N$，表示总内存单元数（即地址范围从 $0$ 到 $N-1$）。

从第二行开始每行描述一个进程的三个整数 $T, M, P$（$M \le N$）。

最后一行用三个 $0$ 表示结束。

数据已按 $T$ 从小到大排序。

输入文件最多 $10000$ 行，且所有数据都小于 $10^9$。

输入文件中同一行相邻两项之间用一个或多个空格隔开。

输出格式

输出包括 $2$ 行。

第一行是全部进程都运行完毕的时刻。

第二行是被放入过等待队列的进程总数。

输入输出样例 #1

输入样例

10
1 3 10
2 4 3
3 4 4
4 1 4
5 3 4
0 0 0

输出样例

12
2

输入输出样例 #2

输入样例

20
1 5 5
2 10 10
3 5 5
0 0 0

输出样例

15
1

限制条件

• 总内存单元数：$N$
• 每个进程：申请时刻 $T$，需要内存数 $M \le N$，运行时间 $P$
• 输入最多 $10000$ 行
• 所有数据 $< 10^9$
• 输入已按 $T$ 从小到大排序

样例解释 #1

内存总大小：10 个单元

进程列表：

1. 时刻 1：申请 3 个单元，运行 10 个时间单位
2. 时刻 2：申请 4 个单元，运行 3 个时间单位
3. 时刻 3：申请 4 个单元，运行 4 个时间单位
4. 时刻 4：申请 1 个单元，运行 4 个时间单位
5. 时刻 5：申请 3 个单元，运行 4 个时间单位

模拟过程：

• 时刻 1：进程1分配内存 0-2（3个单元），结束时刻 11
• 时刻 2：进程2分配内存 3-6（4个单元），结束时刻 5
• 时刻 3：进程3需要 4 个连续单元，但最大连续空闲只有 3 个单元（7-9），进入等待队列（队列进程数+1）
• 时刻 4：进程4分配内存 7（1个单元），结束时刻 8
• 时刻 5：进程2结束，释放内存 3-6 进程5申请 3 个单元，但最大连续空闲只有 2 个单元（3-4），进入等待队列（队列进程数+1） 队列头进程3（需要 4 个单元）可以分配，分配内存 3-6，结束时刻 9
• 时刻 8：进程4结束，释放内存 7 进程5（需要 3 个单元）可以分配，分配内存 7-9，结束时刻 12
• 时刻 9：进程3结束，释放内存 3-6
• 时刻 11：进程1结束，释放内存 0-2
• 时刻 12：进程5结束，释放内存 7-9

最后结束时刻：12 进入过等待队列的进程数：2（进程3和进程5）