【问题描述】
离第一个操作系统OS发布已经没有多少时间了，但它的一些组件还没有完成，内存管理器就是其中之一。根据开发人员的计划，在第一个版本中，内存管理器将非常简单和直观。它将支持三个操作：
-
alloc n —— 分配n个字节内存，返回已分配块的正整数标识符x(x初始值为0，每次分配增长1)
-
erase x —— 删除标识符x所在的块
-
defragment —— 整理空余内存碎片，将所有块尽量靠近内存的开始位置，并保持各自的顺序
在此情况下，内存模型非常简单，它是一个m字节的序列，为了方便起见，从第一个字节到第m字节进行编号。
第一个操作alloc n有一个参数n，表示被分配的内存块大小。在处理此操作时，内存中将分配n个连续字节的空闲块。 如果这些块的数量超过一个，则优先选择最接近内存开始(即第一个字节)的块。 所有这些字节都被标记为非空闲，内存管理器返回一个32位整数数字令牌，代表该块的标识符。 如果不可能分配这样大小的空闲块，则返回NULL。
第二个操作erase x以x为参数，表示某个块的标识符。此操作释放系统内存，将此块的字节标记为空闲以供进一步使用。 如果此标识符没有指向先前分配的块(该块尚未被释放)，则返回ILLEGAL_ERASE_ARGUMENT。
最后一个操作defragment没有任何参数，只会使占用的内存部分更接近内存的开始，而不会更改它们各自的顺序。
在当前的实现中，将使用从1开始的连续整数作为标识符。每个成功的alloc操作过程都应该返回接下来的编号。不成功的alloc操作不影响计数。
编写内存管理器的实现，为每个alloc命令输出返回的值，为所有失败的erase命令输出ILLEGAL_ERASE_ARGUMENT。
【输入形式】
输入数据的第一行包含两个正整数t和m（1<=t<=500, 1<=m<=10(5))，其中t表示需要内存管理器来处理的操作个数，m表示有效的内存字节大小。接下来的t行每一行代表一个操作。
【输出形式】
输出有多行，每行或者是alloc操作的结果，或者是失败的erase操作的结果ILLEGAL_ERASE_ARGUMENT。其顺序与输入的操作次序一致。
【样例输入】
6 10
alloc 5
alloc 3
erase 1
alloc 6
defragment
alloc 6【样例输出】
1
2
NULL
3解题步骤
-
初始化内存步骤：
-
从命令行读取t、m
-
初始化ArrayList v，大小为m，赋值0代表内存空闲。 （使用到ArrayList的.add(i)方法）
-
处理操作：
-
遍历t，从命令行读取操作oper
-
初始化mark = 0，用于标记生成的唯一内存标识符
-
if判断是“alloc”操作
-
从命令行读取需要分配的内存大小size
-
调用alloc方法
-
初始化起始位置start = -1，以防未找到情况
-
找空余位置：循环遍历内存v，并设空余空间为free = 0
-
if判断，当前值是否为空 v.get(i) == 0，如果是，if判断++free == size，是否已经找到size个大小的空余空间，找到的话，更改start起始值 = i - size + 1；break跳出循环因为已经找到距离起始值最近的空闲值
-
如果不是，重制 free = 0；
-
-
空余位置赋值标识符
-
如果没找到，if判断start == -1，输出“NULL”
-
找到
-
为size个内存循环赋值标识符mark+1
-
输出++mark
-
返回mark
-
-
-
-
-
else if判断是erase操作：
-
从命令行读取读取需要释放的内存块标识符id
-
调用erase方法
-
flag = 0
-
遍历内存列表，将所有值等于指定标识符的元素重新标记为0，并将flag = 1（使用到ArrayList的.get(i)方法、.set(i, 0)方法）
-
if判断如果flag = 1，如果没有找到指定标识符的内存块，输出
ILLEGAL_ERASE_ARGUMENT。
-
-
-
defragment操作：
-
调用erase方法执行操作
-
保存当前v的size
-
v.removeIf(n -> n == 0); 移除所有值为0的元素
-
如果内存v.size() < size，添加到足够size的空标识符（使用到ArrayList的.add(i)方法）
-
-
-
输入输出处理：
-
序首先读取操作数量和内存大小，然后根据读入的操作类型调用相应的处理函数。
-
对于每个
alloc操作，输出分配的内存块的标识符；对于失败的erase操作，输出错误信息。
关键点
-
使用ArrayList模拟内存是这个解决方案的核心，它允许我们通过索引直接访问和修改内存的任何部分。
-
维护一个全局的标识符计数器（
mark数组），为每个成功分配的内存块分配一个唯一的标识符。 -
通过遍历和修改ArrayList的方式来实现内存的分配、释放和整理。
Java代码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取操作次数t和内存大小m
int t = scanner.nextInt(), m = scanner.nextInt();
// 初始化内存列表v，大小为m，初始值全部为0表示空闲
List<Integer> v = new ArrayList<>(m);
for (int i = 0; i < m; i++) v.add(0);
// mark用于为每个分配的内存块生成唯一标识符
int mark = 0;
// 循环处理t次操作
while(t-- > 0){
// 读取操作类型
String oper = scanner.next();
if(oper.equals("alloc")){
// 分配内存操作，读取需要分配的大小
int size = scanner.nextInt();
// 调用alloc方法进行内存分配，并更新mark值
mark = alloc(v, size, mark);
}else if(oper.equals("erase")){
// 释放内存操作，读取需要释放的内存块标识符
int id = scanner.nextInt();
// 调用erases方法进行内存释放
erases(v, id);
}else if(oper.equals("defragment")){
// 内存碎片整理操作
defragment(v);
}
}
scanner.close();
}
// alloc方法用于分配内存
private static int alloc(List<Integer> v, int size, int mark) {
int start = -1; // 记录找到的空闲块的起始位置
// 遍历内存列表寻找足够大的连续空闲块
for (int i = 0, free = 0; i < v.size(); i++) {
if (v.get(i) == 0) {
// 空闲块大小增加
if (++free == size) {
// 找到足够大的空闲块，记录起始位置并退出循环
start = i - size + 1;
break;
}
} else {
// 遇到已分配的内存，重置空闲块计数器
free = 0;
}
}
if (start == -1) {
// 未找到足够大的空闲块，输出NULL
System.out.println("NULL");
} else {
// 在找到的空闲块位置分配内存，更新内存块的标识符
for (int i = start; i < start + size; i++) v.set(i, mark + 1);
// 输出分配的内存块标识符
System.out.println(++mark);
}
// 返回更新后的mark值
return mark;
}
// erases方法用于释放内存
private static void erases(List<Integer> v, int id) {
int flag = 0; // 标记是否找到并释放了指定的内存块
// 遍历内存列表，寻找并释放指定标识符id的内存块
for (int i = 0; i < v.size(); i++) {
if(v.get(i) == id){
// 将内存块标记为0，表示释放
v.set(i, 0);
flag = 1;
}
}
if(flag == 0) {
// 如果未找到指定的内存块，输出错误信息
System.out.println("ILLEGAL_ERASE_ARGUMENT");
}
}
// defragment方法用于内存碎片整理
private static void defragment(List<Integer> v) {
int size = v.size();
// 移除所有标记为0的元素（空闲内存）
v.removeIf(n -> n == 0);
// 补回被移除的空闲内存，保持内存大小不变
while(v.size() < size) v.add(0);
}
}
