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

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

优先队列简单应用题。10 min 过了。

将文件按照加入时间从小到大排序，对于每一个文件分别去选打印机。

对于打印机，需要选择当前最早能使用的。开一个堆，按照最早可以使用的时间从小到大排序。堆顶为可使用时间最早的打印机。

对于最早可使用的时间小于 t_i 的打印机，它们对我们来说都无需等待，因此只有编号上的差异。我们将这些打印机的最早使用时间都赋为 0，这样方便按照编号排序。具体的，对于最早可使用时间等于 0 的开一个堆 q，对于最早可使用时间大于 0 的开一个堆 Q，每次将 Q 中的若干个打印机移动到 q 中，并将最早可使用时间设为 0。

处理过后，如果 q 中有打印机，即有不需要等待的，使用 q 中编号最小的打印机。否则使用 Q 中等待时间最短的打印机。

时间复杂度 O(n\log n)。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n, m;
struct File_ { int s, t, id; } a[N];
bool operator < (File_ a, File_ b) {
    return a.t < b.t;
}
struct Print {
    LL now, id;
    bool operator < (const Print &x) const {
        return now > x.now || (now == x.now && id > x.id);
    }
};
priority_queue <Print> q, Q;
// q 中存 0 Q 中存非 0
vector <int> ans[N];
signed main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    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 + n + 1);
    for (int i = 1; i <= m; ++i)
        q.push ({0, i});
    for (int i = 1; i <= n; ++i) {
        if (!Q.empty ()) {
            vector <int> v;
            while (!Q.empty ()) { // 将 Q 中无需等待的打印机移至 q 中
                LL x = Q.top ().now;
                if (x > a[i].t) break;
                v.push_back (Q.top ().id), Q.pop ();
            }
            for (auto j : v) q.push ({0, j});
        }
        int id;
        if (!q.empty ()) { // 有无需等待的
            id = q.top ().id; q.pop ();
            Q.push ({a[i].t + a[i].s, id});
        }
        else { // 需要等待
            id = Q.top ().id;
            Q.push ({Q.top ().now + a[i].s, id});
            Q.pop ();
        }
        ans[id].push_back (a[i].id); // 记录答案
    }
    for (int i = 1; i <= m; ++i) {
        cout << ans[i].size () << ' ';
        sort (ans[i].begin (), ans[i].end ());
        for (auto &j : ans[i]) cout << j << ' ';
        cout << '\n';
    }
    return 0;
}