内存分配

形式化题目

容量为 $N$ 的内存，地址 $0, 1, \dots, N-1$ 连续排列。有 $n$ 个进程，每个进程给出三元组 $(T, M, P)$ ：在时刻 $T$ 申请 $M$ 个单元、上机后连续占用 $P$ 个时间单位，即占据区间 $[T',\ T'+P)$ ，其中 $T'$ 是它实际拿到内存的时刻（可能晚于申请时刻）。数据保证 $M \leqslant N$ ，且申请时刻非降。

分配与等待规则：

分配：某进程申请时，若存在能容纳 $M$ 个单元的空闲地址片，立刻分配，并取首地址最小的那一片（等价于：地址序扫描第一个长度 $\geqslant M$ 的空闲块，从它的起点切走 $M$ 个单元，余量留在原地）。
入队：放不下则进入等待队列尾部。队头优先级最高——只要任一时刻存在容纳得下队头的空闲片，队头立刻出队上机；队列中其它成员不得先于队头被处理。
归还：进程在 $T'+P$ 时刻结束，占用的单元立刻变回空闲。

求两个全局量：全部进程都运行完毕的时刻，以及被放入过等待队列的进程总数（只要进过队列就计入）。

样例（ $N = 10$ ）：

text

输出 2 表示有两个进程进过队列：(3,4,4) 因当时最长空闲只有 3 而入队，(5,3,4) 到达时只差 1 格也入队。结束时刻 12 来自最后上机的 (5,3,4)：它在时刻 8 才拿到内存， $8 + 4 = 12$ 。逐时刻推演见下文思路中的表格。

正解

思路

先看最直观的做法。 模拟分配过程，最容易想到的是沿时间轴逐格推进：now 从 0 每单位时间加一，每个时刻检查有没有进程该归还、有没有进程到达、队头能不能上机。这个做法只在"时间跨度"上花功夫，而题面里 $T$ 、 $P$ 都能到 $10^9$ ——实测数据的结束时刻有 $35970882$ 这样的量级，逐格推进根本跑不完。瓶颈很明确：工作量被时间跨度绑架了，而真正有意义的规模是进程数 $n \leqslant 10000$ 。

改成逐事件推进。 状态只在"事件时刻"变化：两个事件之间，内存布局、队列内容纹丝不动。所以每次直接跳到下一个事件时刻：

\text{下一事件时刻} = \min(\text{下一到达时刻},\ \text{最早释放时刻})

到达事件已按 $T$ 升序给出，用下标顺扫即可；
释放事件在进程上机时才产生，用小根堆按"结束时刻"排序（二叉堆标签的由来）；
派发事件不必单独排队：它只可能紧随内存状态变化发生，把"队头放得下就立刻上机"实现成每次释放之后的循环检查即可，"任一时刻"的无限语义就降成了有限个离散检查点。

事件总数是 $n$ 次到达 $+$ $n$ 次释放 $+$ 至多 $n$ 次队头派发，与 $10^9$ 的时间跨度无关。

同一时刻的处理顺序是本题的正确性核心。 题面没写"同一时刻先做什么"，顺序选错输出就变，只能用样例反推，得到固定三步：

先释放： $T'+P$ 时刻占用已结束，同一时刻的进程可以立即使用这块内存（样例里 $t=5$ 时 B 归还 $[3,7)$ 后，这块空间才存在）；
再派发队头：反复执行"队头放得下就上机"，直到放不下。若颠倒成"先处理到达"， $t=5$ 到达的 (5,3,4) 会 first-fit 抢走刚归还的 $[3,7)$ ，队头 (3,4,4) 只能继续等，结束时刻变成 $13 \ne 12$ ；
最后处理到达：放不下才入队并计数。注意到达者可以越过队头—— $t=4$ 时队头 (3,4,4) 需要 4、空闲只有 $[7,10)$ 长 3，而到达的 (4,1,4) 只要 1，它直接拿走 $[7,8)$ ；若强制"队头放不下时到达者也得排队"，进队总数会变成 $3 \ne 2$ 。"不能越过队头"只约束队列内部成员，新到达走的是另一条申请通道。

空闲区怎么维护。 分配要"首地址最小"，归还要"与相邻空闲块合并"，两者都要求空闲区按地址有序——这正是题面"链表"标签的用意：C++ 里是一条地址升序的空闲块链表，Python 里用 bisect 维护的升序列表同样成立：

alloc(need)：沿地址序扫第一个 size >= need 的块，从起点切走 need，整块用尽就删除；
release(start, size)：bisect 定位插入点，若与左邻首尾恰好相接（左首 + 左长 == start）或与右邻相接（右首 == start + size）就先合并再插回。

占用区只需一个按结束时刻的小根堆，等待队列只需一个 FIFO deque——只有队头会被尝试分配。

下表把官方样例完整走一遍，每行展示该时刻按"释放 → 队头 → 到达"三步处理后的内存与队列（空闲片/占用区间均写作 [首地址, 尾地址)，→ 后是该进程的结束时刻）：

时刻	发生了什么（按释放 → 队头 → 到达）	处理后空闲片	占用中的进程	等待队列（累计进队）
1	A `(3,10)` 到达，first-fit 分到首地址 0	`[3,10)`	A `[0,3)→11`	— （0）
2	B `(4,3)` 到达，分到首地址 3	`[7,10)`	A，B `[3,7)→5`	— （0）
3	C `(4,4)` 到达：最长空闲 3 < 4，入队	`[7,10)`	A，B	C （1）
4	队头 C 放不下（需 4）；D `(1,4)` 到达，越过后分到首地址 7	`[8,10)`	A，B，D `[7,8)→8`	C （1）
5	B 归还 `[3,7)`；队头 C 立刻分到 `[3,7)`；E `(3,4)` 到达，放不下入队	`[8,10)`	A，C `[3,7)→9`，D	E （2）
8	D 归还 `[7,8)`，右并成 `[7,10)`；队头 E 分到 `[7,10)`	空	A，C，E `[7,10)→12`	— （2）
9	C 归还 `[3,7)`	`[3,7)`	A，E	— （2）
11	A 归还 `[0,3)`，左并成 `[0,7)`	`[0,7)`	E	— （2）
12	E 归还 `[7,10)`，并成整段 `[0,10)`，全部结束	`[0,10)`	无	— （2）

重点看第 4、5 行：第 4 行证明到达者能越过放不下的队头（否则 D 也进队，计数变 3）；第 5 行证明同一时刻队头先于到达拿到刚释放的内存（否则 E 抢走 [3,7)，结束时刻变 13）。两行合起来就是三步顺序的完整依据，其余各行只是 first-fit 与合并的机械执行。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 13:04
# update_at: 2026-10-01 13:04

import heapq
import sys
from bisect import bisect_left
from collections import deque

INF = 10**18                          # 大于一切输入时刻的"无穷远"
FREE: list[list[int]] = []            # 地址升序的空闲块 [首地址, 长度]


def alloc(need: int) -> int | None:
    """首地址最小、长度放得下 need 的空闲片：划走 need 并返回首地址；放不下返回 None。"""
    for i, (start, size) in enumerate(FREE):
        if size >= need:
            if size > need:
                FREE[i] = [start + need, size - need]   # 片尾余量留在原地
            else:
                FREE.pop(i)
            return start
    return None


def release(start: int, size: int) -> None:
    """归还 [start, start+size)：按地址插回空闲表，并与左右相邻的空闲块合并。"""
    i = bisect_left(FREE, start, key=lambda block: block[0])
    if i and FREE[i - 1][0] + FREE[i - 1][1] == start:   # 与左邻块衔接
        start, size = FREE[i - 1][0], size + FREE[i - 1][1]
        FREE.pop(i - 1)
        i -= 1
    if i < len(FREE) and FREE[i][0] == start + size:     # 与右邻块衔接
        size += FREE[i][1]
        FREE.pop(i)
    FREE.insert(i, [start, size])


def simulate(N: int, arrive: list[tuple[int, int, int]]) -> tuple[int, int]:
    """事件推进模拟：先释放、再派队头、后处理新到达；返回 (全部结束时刻, 进过队列的进程数)。"""
    FREE.clear()
    FREE.append([0, N])                           # 初始整段空闲
    running: list[tuple[int, int, int]] = []      # 二叉堆 (结束时刻, 首地址, 长度)
    wait: deque[tuple[int, int]] = deque()        # 等待队列 (单元数, 运行时间)
    queued = 0                                    # 放入过等待队列的进程总数
    now, i = 0, 0

    while i < len(arrive) or running:
        # 下一事件时刻：最早到达的进程与最早结束的进程，谁早听谁的
        now = min(arrive[i][0] if i < len(arrive) else INF,
                   running[0][0] if running else INF)

        # 1) 此刻结束的进程全部归还：T+P 时刻它们占的单元已经可用
        while running and running[0][0] == now:
            _, start, size = heapq.heappop(running)
            release(start, size)

        # 2) 队头放得下就立刻上机；队头放不下时，队列里谁也不能越过它上机
        while wait:
            start = alloc(wait[0][0])
            if start is None:
                break                              # 队头还是放不下，后面的进程没资格先上
            m, p = wait.popleft()
            heapq.heappush(running, (now + p, start, m))

        # 3) 时刻 now 到达的进程依次申请：放不下才进队列；直接到达者不受队头约束
        while i < len(arrive) and arrive[i][0] == now:
            m, p = arrive[i][1], arrive[i][2]
            start = alloc(m)
            if start is None:
                wait.append((m, p))                # 进过队列就算数，之后再被弹出也一样
                queued += 1
            else:
                heapq.heappush(running, (now + p, start, m))
            i += 1

    return now, queued                             # 循环结束时 running 已清空，now 即全部结束时刻


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(data)                                 # 总内存单元数，地址 0..N-1

    arrive: list[tuple[int, int, int]] = []        # (申请时刻, 单元数, 运行时间)，已按时刻升序
    while True:
        T, M, P = next(data), next(data), next(data)
        if T == 0 and M == 0 and P == 0:
            break
        arrive.append((T, M, P))

    finish, queued = simulate(N, arrive)
    print(finish)
    print(queued)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 16:15
 * update_at: 2026-10-06 16:15
 */
// 内存分配：逐事件模拟（时间跨度最大 1e9，不能逐时间格推进）。
// 核心结构：
//   1. blocks：地址升序的空闲块表（map<首地址, 长度>），first-fit 取首地址最小的可容纳块；
//   2. occupied：按结束时刻的小根堆，堆顶就是下一个要归还内存的进程；
//   3. 等待队列：FIFO，只有队头会被尝试分配，其它成员不得插队。
// 同一时刻的处理顺序（由样例 12/2 反推）：先释放 -> 再派发队头 -> 最后处理到达。
// 注意：新到达的进程可以越过放不下的队头直接分配（队头约束只作用于队列内部）。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

typedef long long ll;

int n; // 进程个数（不含结束标志 0 0 0）

ll total_n; // 总内存单元数 N

struct Proc {
    ll t; // 申请时刻
    ll m; // 需要的内存单元数
    ll p; // 运行时间
};
Proc procs[MAXN];

map<ll, ll> blocks; // 空闲块表：首地址 -> 长度，按键升序，保证 first-fit 首地址最小

// 释放堆：按 (结束时刻, 首地址, 长度) 排序的小根堆
priority_queue< pair<ll, pair<ll, ll> >,
               vector< pair<ll, pair<ll, ll> > >,
               greater< pair<ll, pair<ll, ll> > > > occupied;

ll wait_q[MAXN]; // 等待队列，存进程下标
int qhead, qtail;

// 在空闲块表中分配 need 个单元：沿地址序扫第一个长度 >= need 的块，
// 从块前端切走 need 个单元，余量留在原地；失败返回 -1。
ll alloc(ll need) {
    for (map<ll, ll>::iterator it = blocks.begin(); it != blocks.end(); it++) {
        if (it->second >= need) {
            ll start = it->first;
            ll rest = it->second - need;
            blocks.erase(it);
            if (rest > 0) blocks[start + need] = rest;
            return start;
        }
    }
    return -1;
}

// 归还 [start, start+len)：插回空闲块表，并与恰好首尾相接的左右邻居合并。
void release(ll start, ll len) {
    // 先试右邻：右邻首地址恰好等于本块尾地址
    map<ll, ll>::iterator rit = blocks.find(start + len);
    if (rit != blocks.end()) {
        len += rit->second;
        blocks.erase(rit);
    }
    // 再试左邻：左邻尾地址恰好等于本块首地址
    map<ll, ll>::iterator lit = blocks.lower_bound(start);
    if (lit != blocks.begin()) {
        lit--;
        if (lit->first + lit->second == start) {
            lit->second += len; // 直接把本块并入左邻，无需新插入
            return;
        }
    }
    blocks[start] = len;
}

void read_input() {
    cin >> total_n;
    n = 0;
    ll t, m, p;
    while (cin >> t >> m >> p) {
        if (t == 0 && m == 0 && p == 0) break;
        n++;
        procs[n].t = t;
        procs[n].m = m;
        procs[n].p = p;
    }
}

void solve() {
    // 初始时整段内存 [0, N) 是一个空闲块
    blocks[0] = total_n;

    ll now = 0;    // 当前事件时刻，也是最后的全部运行完毕时刻
    ll idx = 1;    // 下一个待处理到达的进程下标（数据按 T 升序）
    ll queued = 0; // 进过等待队列的进程总数

    while (idx <= n || !occupied.empty()) {
        // 下一事件时刻 = min(下一次到达时刻, 堆顶最早释放时刻)
        ll t_arr = (idx <= n) ? procs[idx].t : LLONG_MAX;
        ll t_rel = occupied.empty() ? LLONG_MAX : occupied.top().first;
        now = min(t_arr, t_rel);

        // 第 1 步：释放所有结束时刻 == now 的进程（先释放，队头才能用上刚归还的内存）
        while (!occupied.empty() && occupied.top().first == now) {
            release(occupied.top().second.first, occupied.top().second.second);
            occupied.pop();
        }

        // 第 2 步：反复尝试派发队头，放不下立即停止；队列内部不得插队
        while (qhead < qtail) {
            ll id = wait_q[qhead];
            ll start = alloc(procs[id].m);
            if (start == -1) break;
            qhead++;
            occupied.push(make_pair(now + procs[id].p, make_pair(start, procs[id].m)));
        }

        // 第 3 步：处理这一时刻的到达；到达者可越过放不下的队头，失败才入队并计数
        while (idx <= n && procs[idx].t == now) {
            ll start = alloc(procs[idx].m);
            if (start != -1) {
                occupied.push(make_pair(now + procs[idx].p, make_pair(start, procs[idx].m)));
            } else {
                queued++;
                wait_q[qtail++] = idx;
            }
            idx++;
        }
    }

    cout << now << "\n" << queued << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

时间： $O(n \cdot B)$ ，其中 $n$ 为进程数、 $B$ 为并存空闲块数；事件 $O(n)$ 个，每次分配沿地址序扫描 $O(B)$ ，每次归还 $O(\log B)$ 查位加 $O(B)$ 的列表搬运。最坏 $O(n^2)$ ，与 C++ 正解（空闲块链表 first-fit 线性扫描 + 释放二叉堆）同阶；实测 $B$ 远小于 $n$ ，5 组真实数据单例 0.019–0.084s。
空间： $O(n)$ ，空闲块表 $O(B)$ ，释放堆与到达数组各 $O(n)$ ，等待队列 $O(n)$ 。

正确性

内存账本不撒谎：alloc 只从空闲块前端切走单元，块要么消失要么起点右移，不会产生重叠；release 归还的是刚结束进程的真实占用区，且只与恰好首尾相接的邻居合并，不会跨过仍被占用的区段误并。两者维持"占用 $\cup$ 空闲 $= [0, N)$ 且互不相交"。
队列语义精确：wait 是 FIFO，只有队头会被 alloc 尝试，放不下立即 break，队列内不可能插队；而新到达走独立的申请路径，对应"到达者可越过队头"。
事件不漏不重：now 取"下一到达"与"堆顶释放"的较小值，保证不会跳过任何释放；到达按升序逐个消费；弹空 结束时刻 == now 的堆顶后，该时刻的释放必然全部完成。三步顺序正是样例反推出的题面语义。
必然终止且答案正确：每轮要么消费一个到达、要么至少弹出一个释放，下标与堆都单调推进；循环退出即"到达扫完且堆空"，此时 now 恰是最后一个归还时刻，也就是全部进程运行完毕的时刻。

边界	输入	输出	说明
官方样例	$N=10$ 的 5 个进程	`12` / `2`	三步顺序与"越过队头"同时被验证
首进程 $T=0$	memory1	`105` / `1`	唯一进队的 `(4,1,100)` 在 $t=5$ 上机； $t=10$ 到达的 `(10,5,2)` 恰好用满空闲 $[1,6)$ ，不必进队
内存宽裕不入队	memory5（ $N=10000$ ）	`506316` / `0`	`queued` 保持 0，进队计数不等于进程数
高度拥挤	memory3（ $N=100$ ）	`170463` / `6421`	碎片多、队列长，队头阻塞频繁
无任何进程	直接 `0 0 0`	`0` / `0`	事件循环不进，`now` 保持初值 0

总结

本题的本质是把"逐时间格模拟"改写成"逐事件模拟"：状态只在事件时刻变化，于是下一事件时刻取"下一到达"与"堆顶释放"的最小值，工作量从 $10^9$ 的时间跨度降到 $O(n)$ 的事件数。题面的三条规则各对应一个结构——"首地址最小"对应地址升序空闲块表上的 first-fit 扫描，" $T'+P$ 归还"对应释放小根堆，"队头最高优先"对应FIFO 队列加派发循环。最容易做错的是同一时刻的顺序：释放 → 派发队头 → 处理到达，且到达者可以越过放不下的队头——这一条只能从样例的 12 / 2 反推出来，是全题的题眼。

图示解析

这张图串起本题从读入到得到答案的主线：

text

1
2
3
4
5
6
7
8读入 N 与按 T 升序的 (T, M, P) 列表
   `- 事件推进：now = min(下一到达时刻, 堆顶释放时刻)
      |- 1) 释放：弹出所有 结束==now 的占用区，release 按地址插回并与左右邻居合并
      |- 2) 派队头：while 队头 alloc 成功 -> 上机，结束时刻入堆
      |      `- 一旦放不下立即停止；队列内其它进程不得插队
      `- 3) 到达：alloc 成功 -> 上机入堆
             `- alloc 失败 -> 进队尾并计数（到达者不受队头约束，可拿走队头放不下的小空闲片）
   `- 到达扫完 且 释放堆为空 -> now 即全部进程运行完毕的时刻，queued 即进队总数

先看事件节点：min 把"已排序的到达"和"小根堆里的释放"合成一条单调时间线，这是逃离 $10^9$ 时间跨度的唯一入口。中间三个分支是固定顺序的三步，注意第 2 步的 while 与第 3 步的失败分支不对称：队头只能被队列内部的循环服务，而新到达失败才入队、成功就绕过队列——样例的 12 / 2 恰好各验证了其中一半。最后一个节点说明答案的读法：结束时刻来自"堆被排空的那一刻"，进队总数来自第 3 步失败分支的累计。

目录

形式化题目

正解

思路

代码

复杂度

正确性

总结

图示解析