专栏文章

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

zzhujiangyuan
P11289题解参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mir47n5r
此快照首次捕获于
2025/12/04 15:29
3 个月前
此快照最后确认于
2025/12/04 15:29
3 个月前
查看原文
P11289 【MX-S6-T1】「KDOI-11」打印
优先队列简单应用题。10 min 过了。
将文件按照加入时间从小到大排序，对于每一个文件分别去选打印机。
对于打印机，需要选择当前最早能使用的。开一个堆，按照最早可以使用的时间从小到大排序。堆顶为可使用时间最早的打印机。
对于最早可使用的时间小于 tit_i 的打印机，它们对我们来说都无需等待，因此只有编号上的差异。我们将这些打印机的最早使用时间都赋为 00，这样方便按照编号排序。具体的，对于最早可使用时间等于 00 的开一个堆 qq，对于最早可使用时间大于 00 的开一个堆 QQ，每次将 QQ 中的若干个打印机移动到 qq 中，并将最早可使用时间设为 00。
处理过后，如果 qq 中有打印机，即有不需要等待的，使用 qq 中编号最小的打印机。否则使用 QQ 中等待时间最短的打印机。
时间复杂度 O(nlog⁡n)O(n\log n)。
CPP
#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;
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...