bzoj#P3117. [NOI1999]内存分配

[NOI1999]内存分配

题目描述

内存是计算机重要的资源之一,程序运行的过程中必须对内存进行分配。经典的内存分配过程是这样进行的:

  1. 内存以内存单元为基本单位,每个内存单元用一个固定的整数作为标识,称为地址。地址从 00 开始连续排列,地址相邻的内存单元被认为是逻辑上连续的。我们把从地址 ii 开始的 ss 个连续的内存单元称为首地址为 ii 长度为 ss 的地址片。
  2. 运行过程中有若干进程需要占用内存,对于每个进程有一个申请时刻 tt ,需要内存单元数 mm 及运行时间 pp。在运行时间 pp 内(即 tt 时刻开始,t+pt+p 时刻结束),这 mm 个被占用的内存单元不能再被其他进程使用。
  3. 假设在 tt 时刻有一个进程申请 mm 个单元,且运行时间为 pp ,则:
    1. tt 时刻内存中存在长度为 mm 的空闲地址片,则系统将这 mm 个空闲单元分配给该进程。若存在多个长度为 mm 个空闲地址片,则系统将首地址最小的那个空闲地址片分配给该进程。
    2. . 如果 tt 时刻不存在长度为 mm 的空闲地址片,则该进程被放入一个等待队列。对于处于等待队列队头的进程,只要在任一时刻,存在长度为 mm 的空闲地址片,系统马上将该进程取出队列,并为它分配内存单元。注意,在进行内存分配处理过程中,处于等待队列队头的进程的处理优先级最高,队列中的其它进程不能先于队头进程被处理。

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

输入格式

第一行是一个数 nn,表示总内存单元数(即地址范围从 00n1n-1 )从第二行开始每行描述一个进程的三个整数 t,m,pt,m,p数据已按 tt 从小到大排序。

最后一行用 0 0 0 表示结束。

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

输出格式

共两行。第一行是全部进程都运行完毕的时刻。第二行是被放入过等待队列的进程总数。

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

数据规模与约定

对于 100%100\% 的数据,mn m \le n。输入文件最多 10410^4 行,且所有数据都小于 10910^9