优质码风+链表做法

· · 题解

思路：

​ 由于本题输入行数不超过 10000，所以任何时刻占用了内存的块至多会将块整个内存划分成 20000 个相间的 空块与实块。因为还要支持空实块的插入与删除，自然而然可以想到 链表。

​ 起始时只有一个长度为 n 的空块，每一次先将能弹出的块先释放内存，合并连续的空块，同时按题目要求尽早把等待队列中的块放入内存，最后尝试放入当前块。没有块加入后，直接把等待队列处理完即可。

​ 处理的过程中，每次记录释放块时时间的最大值，同时暂时无足够内存的放入等待队列后记录数量，最后输出答案即可。

​ 具体实现见代码，有详细批注。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
const int N = 20010;
struct P {
    int s, t, f;    // 起始地址，块的长度，是否为空（0/1）
    int l, r;   // 该块的左右指针
}p[N];
priority_queue<PII, vector<PII>, greater<PII> > q1;     // 已匹配内存的块的释放空间队列：{释放时间，块编号} 。 
queue<PII> q2;  // 等待队列：{块长度，块存在时间}。
int n, idx, ans1, ans2;
void add(int k, int u) {    // 添加块 
    p[u].r = p[k].r;
    p[p[k].r].l = u;
    p[k].r = u;
    p[u].l = k;
}
void D(int k) {     // 删除块 
    p[p[k].r].l = p[k].l;
    p[p[k].l].r = p[k].r;
}
bool work(int s, int len, int t) {  // 尝试将：起始时间为 s，长度为 len，占用时间为 t，的块匹配内存。 
    int la = 0;
    for (int i = p[0].r; i != N - 1 && i; i = p[i].r) {
        if (!p[i].f && p[i].t >= len) {     // 该块可以放入 
            int u = ++ idx;     // 建立一个新块
            p[u].s = p[i].s, p[u].t = len, p[u].f = 1;  // 初始该块信息
            p[i].s += len, p[i].t -= len;   // 当该实块占用了空块的一部分时，优先会占用靠前的一部分，所以空块会右移。
            add(la, u);
            q1.push({t + s, u});
            return true;    // 匹配成功
        }
        la = i;
    }
    return false;   //匹配失败
}
void merge() {  // 合并分开的空块 
    for (int i = p[0].r; i != N - 1 && i; i = p[i].r) {
        if (!p[i].f && !p[p[i].r].f) {
            p[i].t += p[p[i].r].t;  //将后一个空块的长度累加到前一个上
            D(p[i].r);  // 删除两空块中后一个。
            i = p[i].l;     //  注意！！！这里一定要向前缩一下，这样才能处理完多个连续的空块 
        }
    }
}
void Work() {   // 通过释放空间来尝试放入后来的块 
    int T = q1.top().first; // 释放时间
    while (q1.size() && q1.top().first == T) {  // 同一时间释放的要一起释放然后在尝试能否加入块
        int u = q1.top().second;
        p[u].f = 0;     // 更改为空块
        q1.pop();
    }
    merge();    // 释放空间后需要合并空块 
    // 若等待队列不为空，且可以成功占用内存
    while (q2.size() && work(T, q2.front().first, q2.front().second))
        ans1 = max(ans1, T + q2.front().second), q2.pop();  // 记录答案
}
signed main() {
    cin >> n;
    p[0] = {0, 0, 1, 0, N - 2}; // 左哨兵
    p[N - 1] = {n + 1, 0, 1, N - 2, 0}; //右哨兵
    p[N - 2] = {0, n, 0, 0, N - 1};     // 初始空块
    while (1) {
        int a, b, c; //申请时刻、长度、时间。 
        cin >> a >> b >> c;
        if (!a && !b && !c) break;
        while (q1.size() && q1.top().first <= a) Work();    // 尝试放入等待队列中的块
        merge();
        if (!work(a, b, c)) q2.push({b, c}), ans2 ++;   // 尝试放入当前块
    }
    while (q2.size()) Work();   // 最后处理等待队列中的剩余
    while (q1.size()) ans1 = max(ans1, q1.top().first), q1.pop();   // 记录释放队列剩余答案
    cout << ans1 << '\n' << ans2;
    return 0;
}
/*
内部核心步骤：
1：将到时间的块弹出。
2：合并空时间块。
3：检查当前是否有可以等待队列中的可放入的。
4：尝试放入当前块，若不可，将其放入等待队列。
*/

求指出问题，求赞，求管理员通过。