赛时一个小时才过。

题目链接

思路分析

首先很容易想到用一个堆来维护所有的打印机，然后将所有任务按照下发时间升序排序来模拟整个过程。

然后考虑堆除了编号之外维护什么东西。

一种想法是维护每个打印机到当前任务需要等多久，但这样每次都需要更新一变，时间复杂度为 O(nm\log m)。

发现可以维护每个打印机当前的最后一个任务的结束时间，在堆中首先按照结束时间升序排序，结束时间相同再按照编号。这样又会出现一个问题就是当有打印机在这个任务之前结束时，事实上它们对于这个任务的等待时间都是 0，此时应按照编号排序，但是在堆中会按照打印机中上一个任务的结束时间排序，这样就不对了。

于是我们考虑维护两个堆，分别维护对于当前任务不需要等待和需要等待的打印机。枚举每一个任务，如果第一个堆中有打印机那就用这个打印机并把它加入第二个堆，否则就用第二个堆中的堆顶打印机。

每次操作第二个堆最多加入一个元素，减少 m 个元素；第一个堆最多加入 m 个元素，减少一个元素。均摊下来是 O(n\log m) 的。堆的话不想手写用优先队列就行了。

代码

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

const int maxn=200003;

int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>57||ch<48){
        if(ch==45){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>=48&&ch<=57){
        x=(x<<1)+(x<<3)+(ch-48);
        ch=getchar();
    }
    return x*f;
}

struct node{
    int s,t,idx;
}a[maxn];

bool cmp(node x,node y){
    return x.s<y.s;
}

int n,m;

vector<int>ans[maxn];

priority_queue<pair<int,int> >q2;
priority_queue<int>q1;

signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        a[i].t=read(),a[i].s=read();
        a[i].idx=i;
    }
    for(int i=1;i<=m;i++){
        q1.push(-i);
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        while((!q2.empty())&&-q2.top().first<=a[i].s){
            q1.push(q2.top().second);
            q2.pop();
        }
        if(q1.empty()){
            int id=-q2.top().second,tim=-q2.top().first;
            q2.pop();
            ans[id].push_back(a[i].idx);
            q2.push(make_pair(-tim-a[i].t,-id));
        }else{
            int id=-q1.top();
            ans[id].push_back(a[i].idx);
            q1.pop();
            q2.push(make_pair(-a[i].s-a[i].t,-id));
        }
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i].size()<<' ';
        sort(ans[i].begin(),ans[i].end());
        for(int j=0;j<ans[i].size();j++){
            cout<<ans[i][j]<<' ';
        }
        cout<<"\n";
    }
    return 0;
}