题目名称 | 284. [NOI 1999]内存分配 |
---|---|
输入输出 | memory.in/out |
难度等级 | ★★☆ |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试数据 | 5 |
题目来源 | BYVoid 于2009-02-25加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:15, 提交:75, 通过率:20% | ||||
TA | 100 | 0.017 s | 5.34 MiB | C++ |
TA | 100 | 0.018 s | 4.28 MiB | C++ |
Ufowoqqqo | 100 | 0.030 s | 46.09 MiB | C++ |
Rivendell | 100 | 0.033 s | 0.39 MiB | C++ |
QhelDIV | 100 | 0.034 s | 1.19 MiB | C++ |
TA | 100 | 0.045 s | 4.37 MiB | C++ |
再见 | 100 | 0.050 s | 1.91 MiB | C++ |
浮生随想 | 100 | 0.067 s | 80.61 MiB | C++ |
BYVoid | 100 | 0.075 s | 0.72 MiB | C++ |
TA | 100 | 0.078 s | 123.12 MiB | C++ |
关于 内存分配 的近10条评论(全部评论) | ||||
---|---|---|---|---|
不会打正解只能裸线段树的蒟蒻只能默默打了个表……
浮生随想
2016-10-31 19:32
4楼
| ||||
天啊!!!!!!!!!10几遍终于通过了!!!
注意:在一个时刻先把所有该时刻完成的程序停止,然后再处理等待队列 【说好的任意一个时刻只有有空间就插进去呢
再见
2016-01-23 19:59
3楼
| ||||
回复 @CreationAugust :
跪CA爷
fye
2015-08-10 19:37
2楼
| ||||
回复 @CreationAugust :
跪ca爷。
TA
2015-08-10 14:30
1楼
|
内存是计算机重要的资源之一,程序运行的过程中必须对内存进行分配。
经典的内存分配过程是这样进行的:
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 \le N$)。
数据已按 $T$ 从小到大排序。
最后一行用 0 0 0表示结束。
输入文件最多 $10000$ 行,且所有数据都小于 $10^9$。
输入文件中同一行相邻两项之间用一个或多个空格隔开。
共两行。
第一行是全部进程都运行完毕的时刻。
第二行是被放入过等待队列的进程总数。
10 1 3 10 2 4 3 3 4 4 4 1 4 5 3 4 0 0 0
12 2