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

· · 题解

闲话：大样例以及 60 分的数据，全都是不需要等待的情况。所以你咋写挂都能过大样例。太神秘了。

首先将所有打印任务按照 t 升序排序。

注意到若不需要等待，选编号最小的。若需要等待，选等待时间最短的。看上去非常优先队列。我们开两个优先队列 q_1,q_2 分别维护需要等待的打印机，能直接使用的打印机。维护它们的编号和可使用的时间戳。判定能否直接使用只需比较时间戳和 t 的大小即可。

初始化 m 个打印机都是可直接使用的，全部放入 q_2 中，时间戳为 0。按照编号升序排序。

每个打印机决策前，首先将 q_1 中可使用的打印机扔到 q_2 中，如下。

while(wait.size() && wait.top().first <= t)
{
    release.push(PII(wait.top().second,wait.top().first));wait.pop();
}

其中，wait 为需要等待的打印机，release 为可直接使用的打印机。wait 的 first,second 分别为可使用的时间戳，打印机编号。按照时间戳升序排序。release 的 first,second 分别为为打印机编号和时间戳。按照打印机编号升序排序。

接下来，若 q_2 中有元素，直接取队头即可。注意修改其时间戳。若修改后的时间戳，大于下一次任务的起始时间，就把它扔到 q_1 中。

若 q_2 中没有元素，该如何处理？此时必须要等待了。我们从 q_1 中找到时间戳最小的打印机即可。注意，时间戳最小的打印机并不一定唯一，若有多个最小的，需使用编号最小的！

if(!release.size()) 
{
    priority_queue <PII,vector<PII>,greater<PII> > printer;
    int flag = wait.top().first;
    printer.push(PII(wait.top().second,wait.top()first));
    wait.pop();
    while(wait.top().first == flag){printer.push(PII(wait.to().second,wait.top().first));wait.pop();}
    release.push(PII(printer.top().first,flag));
    printer.pop();
    while(!printer.empty()){wait.push(PII(printer.top()second,printer.top().first));printer.pop();}
    }

实现略微繁琐。仅供参考。

完整代码如下。

namespace solution
{
    typedef pair<int,int> PII; // time,number
    struct ASK
    {
        int s,t,num;
        bool operator<(const ASK &a)const{
            return t < a.t;
        }
    };
    vector <ASK> ask;
    vector <int> ans[N];
    priority_queue <PII,vector<PII>,greater<PII> > wait,release;
    int n,m;
    int tot = 0; //wait:time,number
    void solve()
    {
        n = read<int>(),m = read<int>();
        for(int i=1;i<=n;i++) {int s,t; s = read<int>(),t = read<int>();ask.push_back({s,t,i});}
        for(int i=1;i<=m;i++) release.push(PII(i,0)); //number,time
        sort(ask.begin(),ask.end());
        for(auto [s,t,num]:ask)
        {
            while(wait.size() && wait.top().first <= t){release.push(PII(wait.top().second,wait.top().first));wait.pop();}
            if(!release.size()) 
            {
                priority_queue <PII,vector<PII>,greater<PII> > printer;
                int flag = wait.top().first;
                printer.push(PII(wait.top().second,wait.top().first));
                wait.pop();
                while(wait.top().first == flag){printer.push(PII(wait.top().second,wait.top().first));wait.pop();}
                release.push(PII(printer.top().first,flag));
                printer.pop();
                while(!printer.empty()){wait.push(PII(printer.top().second,printer.top().first));printer.pop();}
            }
            ans[release.top().first].push_back(num);
            auto tt = release.top().second;
            tt = max(release.top().second,t) + s;
            tot ++;
            if(tot >= n) break;
            if(tt > ask[tot].t) {wait.push(PII(tt,release.top().first));release.pop();}
            else 
            {
                int number = release.top().first;
                release.pop();
                release.push(PII(number,tt));
            }
        }
        for(int i=1;i<=m;i++) sort(ans[i].begin(),ans[i].end()); // 输出前记得排个序
        for(int i=1;i<=m;i++) {print(ans[i].size(),' ');for(auto t:ans[i])print(t,' '); puts("");}
    }
}