T01193: 内存分配

implementation, http://cs101.openjudge.cn/practice/01193/

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

内存以内存单元为基本单位，每个内存单元用一个固定的整数作为标识，称为地址。地址从0开始连续排列，地址相邻的内存单元被认为是逻辑上连续的。我们把从地址i开始的s个连续的内存单元称为首地址为i长度为s的地址片。
运行过程中有若干进程需要占用内存，对于每个进程有一个申请时刻T，需要内存单元数M及运行时间P。在运行时间P内（即T时刻开始，T+P时刻结束），这M个被占用的内存单元不能再被其他进程使用。

3、假设在T时刻有一个进程申请M个单元，且运行时间为P，则：

若T时刻内存中存在长度为M的空闲地址片，则系统将这M个空闲单元分配给该进程。若存在多个长度为M个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。
如果T时刻不存在长度为M的空闲地址片，则该进程被放入一个等待队列。对于处于等待队列队头的进程，只要在任一时刻，存在长度为M的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。注意，在进行内存分配处理过程中，处于等待队列队头的进程的处理优先级最高，队列中的其它进程不能先于队头进程被处理。

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

输入

第一行是一个数N，表示总内存单元数（即地址范围从0到N-1）。从第二行开始每行描述一个进程的三个整数T、M、P（M <= N）。最后一行用三个0表示结束。数据已按T从小到大排序。输入文件最多10000行，且所有数据都小于109。输入文件中同一行相邻两项之间用一个或多个空格隔开。

输出

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

样例输入

样例输出

12
2

提示

来源

Noi 99

这是一个经典的内存管理模拟问题（源自 NOI 1999），可以通过离散事件模拟的方法来解决。由于时间跨度可能很大（ $10^{9}$ ），我们不能按秒循环，而是应该根据“进程到达”和“进程结束”这两个关键时间节点来推动模拟进程。

核心解题思路

数据结构选择：
- running_tasks: 一个列表，存储当前正在运行的进程信息 [起始地址, 长度, 结束时刻]。为了方便查找空闲地址片，该列表应始终按起始地址排序。
- finish_heap: 一个最小堆，存储所有当前运行进程的结束时刻。通过堆可以快速找到下一个释放内存的时间点。
- wait_queue: 一个先进先出（FIFO）队列，存储等待分配内存的进程需求 (内存大小, 运行时间)。
内存分配逻辑 (find_gap)：
- 遍历已排序的 running_tasks，检查相邻两个任务之间的间隙。
- 依次检查：第一个任务前的间隙、任务之间的间隙、最后一个任务后的间隙。
- 返回第一个满足长度 $M$ 的间隙起始地址。
时间推进逻辑：
- 每当有一个新进程在 $T$ 时刻到达时：
  - 首先处理所有结束时间 $\leq T$ 的进程。
  - 注意：每当有进程运行结束释放内存时，必须立即检查等待队列队头的进程能否进入内存。如果能，则该进程开始运行，并将其结束时间加入堆。这个过程是连锁反应，直到队头进程无法放入内存为止。
  - 处理完历史任务和等待队列后，再尝试将新到达的进程放入内存。如果放不下，放入等待队列。

Python 代码实现

python

import sys
import heapq
from collections import deque
import bisect

def solve():
    # 使用 fast I/O 读取所有输入
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        N = int(next(it))
    except StopIteration:
        return
        
    # running_tasks: 存储 [start_address, size, finish_time]，按 start_address 排序
    running_tasks = []
    # finish_heap: 存储所有任务的 finish_time，用于快速找到下一个释放内存的时间
    finish_heap = []
    # wait_queue: 存储等待进程的需求 (size, duration)
    wait_queue = deque()
    
    wait_count = 0
    total_max_finish_time = 0

    def find_gap(m):
        """寻找长度为 m 的最小起始地址空闲片"""
        if not running_tasks:
            return 0 if N >= m else -1
        
        # 1. 检查第一个任务之前的空间
        if running_tasks[0][0] >= m:
            return 0
            
        # 2. 检查任务之间的间隙
        for i in range(len(running_tasks) - 1):
            gap_start = running_tasks[i][0] + running_tasks[i][1]
            gap_end = running_tasks[i+1][0]
            if gap_end - gap_start >= m:
                return gap_start
                
        # 3. 检查最后一个任务之后的空间
        last_end = running_tasks[-1][0] + running_tasks[-1][1]
        if N - last_end >= m:
            return last_end
            
        return -1

    def allocate_task(pos, m, finish_t):
        """将任务插入运行列表并更新结束时间堆"""
        nonlocal total_max_finish_time
        # 使用 bisect 保持 running_tasks 按起始地址有序
        bisect.insort(running_tasks, [pos, m, finish_t])
        heapq.heappush(finish_heap, finish_t)
        if finish_t > total_max_finish_time:
            total_max_finish_time = finish_t

    def process_finishes(until_time):
        """处理直到 until_time 为止的所有内存释放和等待队列激活"""
        nonlocal running_tasks
        while finish_heap and finish_heap[0] <= until_time:
            t_f = heapq.heappop(finish_heap)
            
            # 同时处理所有在 t_f 时刻结束的任务（可能释放出更大的连续空间）
            finish_times_to_clear = {t_f}
            while finish_heap and finish_heap[0] == t_f:
                finish_times_to_clear.add(heapq.heappop(finish_heap))
            
            # 释放内存
            running_tasks = [t for t in running_tasks if t[2] not in finish_times_to_clear]
            
            # 优先级最高：检查等待队列队头
            while wait_queue:
                m_q, p_q = wait_queue[0]
                pos = find_gap(m_q)
                if pos != -1:
                    wait_queue.popleft()
                    # 等待队列中的进程从内存释放的时刻 t_f 开始运行
                    allocate_task(pos, m_q, t_f + p_q)
                else:
                    # 如果队头都放不下，根据规则，后面的不能先处理
                    break

    # 主循环：读取每个进程请求
    while True:
        try:
            t_arrival = int(next(it))
            m_size = int(next(it))
            p_duration = int(next(it))
        except StopIteration:
            break
            
        if t_arrival == 0 and m_size == 0 and p_duration == 0:
            break
        
        # 1. 在处理新到达请求前，先释放已经完成的任务并处理等待队列
        process_finishes(t_arrival)
        
        # 2. 尝试分配当前到达的任务
        pos = find_gap(m_size)
        if pos != -1:
            allocate_task(pos, m_size, t_arrival + p_duration)
        else:
            # 放入等待队列
            wait_queue.append((m_size, p_duration))
            wait_count += 1
            
    # 3. 输入结束后，处理完所有剩余任务
    while finish_heap:
        process_finishes(finish_heap[0])

    # 输出结果
    print(total_max_finish_time)
    print(wait_count)

if __name__ == "__main__":
    solve()

关键点解释：

优先级规则：题目规定“处于等待队列队头的进程的处理优先级最高”。这意味着每当内存被释放，我们必须首先尝试满足等待队列。即使新来的进程刚好能放下，如果此时等待队列还有人且释放后队头还没能放下，逻辑上我们也是先处理完历史释放事件才处理新进程。
时间同步：等待队列中的进程其运行时间 $P$ 是从它获得内存的时刻开始计算的，而不是从它申请的时刻 $T$ 。
效率：
- 通过 bisect 维护有序列表，使得插入复杂度为 $O (M)$ 。
- 通过列表推导式清理结束任务，复杂度为 $O (M)$ 。
- 总体复杂度约为 $O (K \times M)$ ，其中 $K$ 为进程总数（10000）， $M$ 为同时运行的最大进程数（受内存总量限制），在 Python 中可在规定时间内完成。
样例分析：
- 在时刻 5，进程 2 (2, 4, 3) 结束释放内存。此时等待队列中有进程 3 (3, 4, 4)。空出的地址片刚好能容纳进程 3，于是进程 3 开始运行，结束时间设为 $5 + 4 = 9$ 。
- 在时刻 8，进程 4 结束，释放空间后满足了等待队列中的进程 5，进程 5 开始运行，结束时间为 $8 + 4 = 12$ 。最后结束时间为 12。

T01193: 内存分配 ​

T01193: 内存分配