题解：P11289 【MX-S6-T1】「KDOI-11」打印

以“时刻”为轴（忘记画轴了），把一个文件当成一个线段，以命令时间为起点，打印时间为长度，这条线段就是 [t_i,t_i+s_i)。注意一条线段表示的区间包括左端点不包括右端点。

例如上图 m=3，现在考虑三条线段，起点分别为 t_i、t_{i+1}、t_{i+2}，长度分别为 s_i、s_{i+1}、s_{i+2}（已经将线段按左端点排序）。

一个“时刻”被线段覆盖的次数，就是这个时刻需要的打印机的数量，所以我们要控制每个时刻的打印机数量小于等于 m。

这时候添加一条线段 i+3。

时刻 t_{i+3} 被覆盖了 4 次，大于打印机的数量，所以不能添加这条线段。于是把这条线段向右平移到右边的黄线上，即最前面的一个右端点，使用线段 i 使用过的打印机。

这下左端点变成了 t_i+s_i，右端点变成了 (t_i+s_i)+s_{i+3}。

那么我们就可以建个优先队列，存每个遍历到的右端点，然后按权值从小到大排序，若权值相等则按线段编号从小到大排序（题目要求的）。

上面那个是“左端点比优先队列里存的右端点都小”的情况，那如果左端点比一些点大呢？这就更简单了，只需要选择编号最小的点就可以了，可以再建一个优先队列维护所有“第一个优先队列里的元素比当前左端点小”的元素。

总而言之，更新完第二个优先队列后，若第二个优先队列里有元素，则取队头并弹出；否则取第一个优先队列的队头并弹出。再把这个线段的右端点加入第一个优先队列。

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

typedef pair <int, int> PII;
const int N = 2e5 + 5, INF = 1e18;

struct node {
    int s, t, id;
} a[N];
bool cmp(node a, node b) {
    return a.t < b.t;
}

struct node2 {
    int tim, id; // 时间，打印机编号 
};
struct cmp2 {
    bool operator() (node2 a, node2 b) { 
        if (a.tim == b.tim) return a.id > b.id;
        return a.tim > b.tim; 
    } // 注意优先队列排序时符号是反着的 
};
struct cmp3 {
    bool operator() (node2 a, node2 b) {
        return a.id > b.id;
    }
};

priority_queue <node2, vector <node2>, cmp2> q; 
priority_queue <node2, vector <node2>, cmp3> q2;
vector <int> ans[N];

signed main() {
    cin.tie(0); ios::sync_with_stdio(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].s >> a[i].t;
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n, cmp);

    for (int i = 1; i <= m; i++) q.push({0, i});

    for (int i = 1; i <= n; i++) {
        while (q.size() && q.top().tim <= a[i].t) {
            q2.push(q.top());
            q.pop();
        }

        if (q2.size()) {
            int tim = q2.top().tim, id = q2.top().id;
            int tim2 = a[i].t + a[i].s;
            q2.pop();

            ans[id].push_back(a[i].id);
            q.push({tim2, id});     
        } else {
            int tim = q.top().tim, id = q.top().id;
            int tim2 = tim + a[i].s;
            q.pop();

            ans[id].push_back(a[i].id);
            q.push({tim2, id});         
        }
    }
    for (int i = 1; i <= m; i++) {
        cout << ans[i].size();
        sort(ans[i].begin(), ans[i].end());
        for (auto v : ans[i]) cout << " " << v;
        cout << "\n";
    }
    return 0;
}

看得出来，因为懒所以部分代码是复制粘贴上一段的（大雾

觉得写的好就点个赞吧。如果有什么问题或者建议也可以发在评论区哦。