Memory Manager（翻译）

2022.1.24

题目链接：

https://acs.jxnu.edu.cn/problem/CF7B

原题：

Memory Manager

 1000ms  65536K

描述：

There is little time left before the release of the first national operating system BerlOS. Some of its components are not finished yet — the memory manager is among them. According to the developers' plan, in the first release the memory manager will be very simple and rectilinear. It will support three operations:

• alloc n — to allocate n bytes of the memory and return the allocated block's identifier x;
• erase x — to erase the block with the identifier x;
• defragment — to defragment the free memory, bringing all the blocks as close to the beginning of the memory as possible and preserving their respective order;

The memory model in this case is very simple. It is a sequence of m bytes, numbered for convenience from the first to the m-th.

The first operation alloc n takes as the only parameter the size of the memory block that is to be allocated. While processing this operation, a free block of n successive bytes is being allocated in the memory. If the amount of such blocks is more than one, the block closest to the beginning of the memory (i.e. to the first byte) is prefered. All these bytes are marked as not free, and the memory manager returns a 32-bit integer numerical token that is the identifier of this block. If it is impossible to allocate a free block of this size, the function returns NULL.

The second operation erase x takes as its parameter the identifier of some block. This operation frees the system memory, marking the bytes of this block as free for further use. In the case when this identifier does not point to the previously allocated block, which has not been erased yet, the function returns ILLEGAL_ERASE_ARGUMENT.

The last operation defragment does not have any arguments and simply brings the occupied memory sections closer to the beginning of the memory without changing their respective order.

In the current implementation you are to use successive integers, starting with 1, as identifiers. Each successful alloc operation procession should return following number. Unsuccessful alloc operations do not affect numeration.

You are to write the implementation of the memory manager. You should output the returned value for each alloc command. You should also output ILLEGAL_ERASE_ARGUMENT for all the failed erase commands.

输入：

The first line of the input data contains two positive integers t and m (1 ≤ t ≤ 100;1 ≤ m ≤ 100), where t — the amount of operations given to the memory manager for processing, and m — the available memory size in bytes. Then there follow t lines where the operations themselves are given. The first operation is alloc n (1 ≤ n ≤ 100), where n is an integer. The second one is erase x, where x is an arbitrary 32-bit integer numerical token. The third operation is defragment.

输出：

Output the sequence of lines. Each line should contain either the result of alloc operation procession , or ILLEGAL_ERASE_ARGUMENT as a result of failed erase operation procession. Output lines should go in the same order in which the operations are processed. Successful procession of alloc operation should return integers, starting with 1, as the identifiers of the allocated blocks.

翻译：

描述：

在第一个国家操作系统BerlOS释放之前只还剩下一点时间了。它的一些组成部件还没有完成---这个内存管理器就是这些部件中的一个。根据开发者的计划，在第一个发布的版本中，内存管理器将非常简单且线性。它将支持三个操作系统：

alloc n---分配n个字节的内存并返回已分配的块标识符x；

erase x---擦除标识符为x的块；

defragment---整理空闲的内存，尽可能将所有的内存块靠近内存的开头并且保留它们各自的顺序；

这个内存模型在这个样例中非常简单。它是一个由m个字节组成的序列，为了方便起见，把它们从第1到第m进行编号。

第一个操作alloc n将被分配的内存块大小作为唯一的参数。在处理这个操作的同时，将一个连续n个字节的空闲内存块分配到内存中。如果这些块的数量超过了一个，那么最接近内存开头的这个块是更好的。所有这些字节都被标记为非空闲，并且这个内存管理器返回一个是这个块的标识符的32比特的整数数值。如果分配一个这样大小的空闲的块不可能的话，那么函数返回NULL。

第二个操作erase x的参数是某个块的标识符。这个操作释放了系统的内存，标记这个块的字节为空闲为了以后的使用。在这种情况下，当标识符没有指向被分配的块时，它也没有被擦除，函数返回ILLEGAL_ERASE_ARGUMENT。

最后一步操作整理没有任何争议并且只是让被占用的内存部分更接近内存开始的部分，而不改变它们各自的顺序。

在当前执行中，你将使用连续的整数，以1开始，作为标识符。

每个成功的alloc操作过程将返回接下来的数字。

不成功地alloc操作不影响编号。

你将写下这个内存管理器的执行。你应该为每个alloc操作输出被返回的值。你应该为所有失败的erase操作输出ILLEGAL_ERASE_ARGUMENT。

输入：

第一行输入数据包含两个正整数t和m（1<=t<=100;1<=m<=100），这里的t---是被给的对内存管理器处理的操作次数，这里的m---是可用的内存大小。然后接下来的t行，其中给出了操作本身。第一个操作是alloc n（1<=n<=100），n是一个整数。第二个操作是erase x，这里的x是被给的任意32位整数数值。第三个操作是defragment。

输出：

输出每一行的次序。每行应该包括alloc操作过程的结果，或者输出失败的erase操作过程的结果ILLEGAL_ERASE_ARGUMENT。输出行结果应该按照被操作过程的顺序输出。成功的alloc操作过程应该返回整数，以1开始的，作为被分配块的标识符。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！