P2582. 简易内存池

解题思路

动态模拟

本题是一道非常典型的系统设计题目。 我们需要设计一个简易内存池，支持两种操作：

• 分配内存，对应 REQUEST 操作
• 释放内存，对应 RELEASE 操作

每一行的输入都对应一个操作，我们需要动态模拟该简易内存池的变化。

类似于【贪心】2023C-堆内存申请，我们可以用若干区间来表示该内存池的分配情况。例如：

可以用以下 lst 列表来表示内存池的占用情况：

我们可以通过修改 lst 中的区间，来表示当前内存池的分配情况。 这些区间是左闭右开区间，如二元组 [3, 5] 表示从 3 作为起始位置，长度为 2 的区间，5 不包含在区间内。

已知内存池的总大小为 100，为了方便后续操作，我们可以在 lst 中固定两个不会发生修改的区间 [-1, 0] 和 [100, 101]，即上述例子修改为：

其中重要的元素是 [-1, 0] 中的 0 以及 [100, 101] 中的 100，分别限制了整个内存池的起始和终止位置。

题目给出了 n 个操作，每一个操作都包含具体的操作（"REQUEST" 或 "RELEASE"）以及对应的数字 num（对应分配内存的长度或释放内存的首地址），因此整个动态模拟的整体框架可以用如下方式完成：

剩下的事情只需要填充分配内存和释放内存的对应操作函数即可。

---

内存分配

内存分配的方式和【贪心】2023C-堆内存申请相似但略有不同。 申请的优先级是：在空间足够的前提下，优先从低地址分配。以下面例子为例：

• 如果想申请长度为 1 的内存空间，区间 [1, 3] 是空间足够且最低的首地址，会在地址 1 处进行分配
• 如果想申请长度为 2 的内存空间，区间 [1, 3] 是空间足够且最低的首地址，会在地址 1 进行分配
• 如果想申请长度为 3 的内存空间，区间 [7, 10] 是空间足够且最低的首地址，会在地址 7 进行分配

显然我们可以通过两个相邻间隔中，前一个间隔的 end，和后一个间隔的 start，来得到空闲内存的情况。

对应每一次内存申请操作，我们需要做如下操作：

1. 特殊情况判断，判断待分配的内存长度 num 是否为 0，若为 0 则直接返回 "error" 2. 从左往右遍历整个 lst 数组 3. 在每一步的遍历过程中：

• 获得第 i 个已分配区间 [cur_start, cur_end]（当前区间）和第 i+1 个已分配区间 [nxt_start, nxt_end]（下一个区间）
• 计算两个区间之间的空闲内存长度 nxt_start - cur_end
• 若 nxt_start - cur_end >= num，说明这个空闲内存长度足够分配一个长度为 num 的内存，将即将分配的这个内存块 [cur_end, cur_end + num] 插入到 lst 数组中 i+1 的位置
• 分配完毕后，返回该内存块的首地址 cur_end

4. 若退出循环后仍然没有顺利分配内存，则返回 "error"

可以将上述内存申请操作封装为 request() 函数，即：

---

内存释放

内存释放的操作相对简单，我们同样需要遍历 lst 数组中的区间 [cur_start, cur_end]，当发现 cur_start 等于待删除的内存的首地址 num 时，则在 lst 中删除该区间。可以将该过程封装在 release() 函数中：

复杂度分析 设操作条数为 n。代码用有序列表 lst 维护已分配的区间，并固定 [-1, 0] 与 [100, 101] 两个哨兵区间。由于题解中说明内存池总大小为 100，任一时刻已分配区间的个数 k 存在常数级上界（每块至少占 1 个单位，加上 2 个哨兵不超过 102 个）。request 操作从左到右扫描相邻区间之间的空隙，找第一个能容纳 num 的位置，扫描 O(k)；找到后 list.insert 需要把后续元素整体后移，也是 O(k)。release 操作同样线性扫一遍找首地址匹配的区间，再 remove 删除，代价 O(k)。于是单次操作代价 O(k)，n 次操作总时间 O(n·k)：把 k 视为受总容量 100 限制的常数时整体接近 O(n)；即使不利用这个上界，最坏也只是 O(n²) 量级。空间上，lst 至多存 k 个区间，ans 至多存 n 条输出，operations 存 n 条命令，空间复杂度 O(n)。瓶颈在 request/release 对 lst 的线性扫描与插入删除；代码注释也提到，因为 lst 按地址有序，release 的查找可以改用二分查找加速到 O(log k)，但本题规模下没有必要。