代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Task // 进程
{
    int t1, t2;
    int len;
    int last;
    int id;
    bool operator > (const Task &x) const
    {
        return t2 > x.t2;
    }
};

queue<Task> q1;
priority_queue<Task, vector<Task>, greater<Task>> q2;

struct Piece
{
    bool usable;
    int len;
    int pre, next;
};

#define head list[0].next
#define tail list[0].pre
vector<Piece> list;

void insert(int i, Piece x)
{
    Piece &cur = list[i];
    x.pre = i;
    x.next = cur.next;
    list[cur.next].pre = list.size();
    cur.next = list.size();
    list.push_back(x);
}

void erase(int i)
{
    Piece &cur = list[i];
    list[cur.pre].next = cur.next;
    list[cur.next].pre = cur.pre;
}

void release(int i)
{
    Piece &cur = list[i];
    cur.usable = true;

    if (list[cur.pre].usable)
    {
        cur.len += list[cur.pre].len;
        erase(cur.pre);
    }

    if (list[cur.next].usable)
    {
        cur.len += list[cur.next].len;
        erase(cur.next);
    }
}

bool ask(Task task)
{
    for (int i = head; i; i = list[i].next)
    {
        if (list[i].usable && list[i].len >= task.len)
        {
            if (list[i].len > task.len)
            {
                Piece split_piece{true, list[i].len - task.len};
                insert(i, split_piece);
                list[i].len = task.len;
            }

            list[i].usable = false;
            task.id = i;
            q2.push(task);
            return true;
        }
    }

    return false;
}

int main()
{
    int n;
    cin >> n;
    list.push_back({false, 0, 1, 1});
    list.push_back({true, n, 0, 0});

    int t, m, p;
    int ans1 = 0;
    int ans2 = 0;
    do
    {
        // 读入新任务
        if (t || m || p) cin >> t >> m >> p;
        Task cur{t, t + p - 1, m, p};

        // 解决旧任务
        while (!q2.empty() && (!t || q2.top().t2 < cur.t1))
        {
            Task tp = q2.top();
            q2.pop();
            release(tp.id);
            ans1 = max(ans1, tp.t2);

            if (q2.empty() || q2.top().t2 > tp.t2)
            {
                while (!q1.empty())
                {
                    q1.front().t1 = tp.t2 + 1;
                    q1.front().t2 = tp.t2 + q1.front().last;
                    if (ask(q1.front())) q1.pop();
                    else break;
                }
            }
        }

        // 加入新任务
        if ((t || m || p) && !ask(cur))
        {
            cur.t1 = cur.t2 = 0;
            q1.push(cur);
            ++ans2;
        }
    } while (!q1.empty() || !q2.empty());

    cout << ans1 + 1 << endl << ans2 << endl;
    
    return 0;
}

代码解释

类型

首先我定义了结构体 Task和Piece。

Task的表示一个进程。我的程序中所有进程用的是 Task 类型。参数 t1、t2是开始时间和结束时间（左闭右闭），last是持续时间，len是占用大小，id是对应到list中的位置（先不用管id）。

Piece则表示一个内存片，即一段内存。len 表示内存片大小，usable表示是否可以。我是把它们都存进了链表里边，方便之后合并和分裂。

队列

代码中共有队列q1和优先队列q2。

q1是等待队列，详见题目描述。

q2是运行中的进程序列，也就是正在占用内存的序列。q2是优先队列，按照结束时间升序排序，这样方便结束时顺次弹出。

链表的主要使用逻辑

• 连续的可用内存片尽可能合并为一个大的内存片
• 连续的不可以内存片不能合并，与q2中的进程一一对应（上文所述的id就是从q2中元素到链表中元素的对应关系）

函数

• void insert(int i, Piece x)：链表元素i后面插入x。
• void erase(int i)：删除链表中的元素 i。
• void release(int i)：释放链表元素i对应的内存，包含两个步骤：
  • 释放内存
  • 尝试合并左、右侧的内存片（这里我想过q2中id在合并后对应不上的问题，不存在，q2中对应的内存片一定被占用）
• bool ask(Task task)：尝试把进程task加入内存，返回是否成功。

主函数逻辑

分为多步。

首先要将之前积存的应该结束的运行中进程结束，释放内存，释放出来的内存可以供给队头元素。

注意：如果同一时刻有多个进程同时结束，一定要等它们都结束了再加入新元素

如果此时有新任务，则加入新任务，失败则入队。

注意：如果同一时刻等待队列队头和新任务都可以进内存，有限等待队列队头元素

输出ans1和ans2。

注意：如果你和我一样用了左闭右闭结构，那么答案需要加 1

提交结果

样例过了，提交后爆零，下载后本地也过，但是交上去不行。结果：5 个 WA

谢谢，你不需要帮助我调试代码，把我的思路忘掉吧

我发这个帖子只是想问一下，为什么会出现本地测试下载的样例能过，提交后却会错误。

WA 样例

以下是我下载的测试用例 #1：

输入

6
0 4 2
1 2 4
2 2 3
3 2 2
4 1 100
10 5 2
0 0 0

答案输出

105
1

我的输出

105
1

其他可能出现的问题

当然我有可能是下载错了或者出现其他问题，你可以看一下这个提交记录：https://www.luogu.com.cn/record/227093494