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

思路：用两个优先队列，一个维护当前可以选的最小的打印机，一个处理正在被使用的打印机，按发起时间排序后，每次让时间跳到下一个发起时间，当然要考虑没有打印机可以用时让时间跳到等待时间最小的打印机的结束时间。

当时在自己电脑上跑不用快写跑的超级慢……不过不用也可以拿满。

关于优先队列排序结构体可以看我这篇专栏 关于优先队列中结构体中重载运算符的问题

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
struct wq
{
    ll id,t;
    bool operator < (const wq &a)const
    {
        return t>a.t;
    }
}o;
ll cnt,n,m,t=1,id,temp[N];
priority_queue<ll,vector<ll>,greater<ll> > q;
priority_queue<wq> v;
vector<ll> vec[N];
struct node
{
    ll s,t,id;
}a[N];
bool cmp(node a,node b)
{
    return a.t<b.t;
}
ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x*=10,x+=c-'0';
        c=getchar();
    }
    return x*f;
}
inline void print(ll x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        print(x/10);
    }
    putchar(x%10+'0');
}
int main()
{
    freopen("print4.in","r",stdin);
    freopen("print.out","w",stdout);
    n=read(),m=read();
    for(ll i=1;i<=n;i++)
    {
        a[i].s=read();
        a[i].t=read();
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    for(ll i=1;i<=m;i++)
    {
        q.push(i);
    }
    for(ll i=1;i<=n;i++)
    {
        t=max(a[i].t,t);
        while(!v.empty()&&v.top().t<=t)
        {
            q.push(v.top().id);
            v.pop();
        }
        if(q.empty()) t=v.top().t;
        while(!v.empty()&&v.top().t<=t)
        {
            q.push(v.top().id);
            v.pop();
        }
        id=q.top();
        q.pop();
        o.id=id,o.t=t+a[i].s;
        v.push(o);
        vec[id].push_back(a[i].id);
    }
    for(ll i=1;i<=m;i++)
    {
        print(vec[i].size());
        putchar(' ');
        ll len=vec[i].size();

        for(ll j=0;j<vec[i].size();j++) temp[j]=vec[i][j];
        sort(temp,temp+len);
        for(ll j=0;j<vec[i].size();j++) print(temp[j]),putchar(' ');
        putchar('\n');
    }

    return 0;
 }