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

· · 题解

建两个 priority queue 维护无和有印刷任务的打印机。

const ll N=2e5+10;
ll n,m;

struct item {
    ll l,t,no;
} a[N];

bool cmp(item x,item y) {
    return x.t<y.t;
}

pqueue(ll,greater) pq1;

struct printer {
    ll no,t;

    reset < (printer x) const {
        if(t!=x.t) return t<x.t;
        else return no<x.no;

        //有任务的打印机也要选择尽可能选小编号 
    }

    reset > (printer x) const {
        if(t!=x.t) return t>x.t;
        else return no>x.no;
    }
};

pqueue(printer,greater) pq2;
vector<ll> ans[N];

void print1(auto x){
    while(x.empty()==0){
        cout<<x.top()<<' ';
        x.pop();
    }
}

void print2(auto x){
    while(x.empty()==0){
        cout<<x.top().no<<' '<<x.top().t<<'\n';
        x.pop();
    }
}

int main() {
//  fin;
//  fout;
    cin>>n>>m;

    rep(i,1,n) {
        cin>>a[i].l>>a[i].t;
        a[i].no=i;
    }

    sort(a+1,a+n+1,cmp);

    rep(i,1,m) pq1.push(i);

    rep(i,1,n){
//      cout<<"pq1:";
//      print1(pq1);
//      cout<<"\npq2:\n";
//      print2(pq2);
//      endl;
//      pause;

        while(1){
            if(pq2.empty()==0 and pq2.top().t<=a[i].t){
                pq1.push(pq2.top().no);
                pq2.pop();
            }else break;
        }

        if(pq1.empty()==0){
            ll cur;
            xtop(cur,pq1);
            ans[cur].pb(a[i].no);
            printer new1;
            new1.no=cur;
            new1.t=a[i].t+a[i].l;
            pq2.push(new1);
        }else{
            printer cur;
            xtop(cur,pq2);
            ans[cur.no].pb(a[i].no);
            cur.t+=a[i].l;
            //如果打印机的任务在此文件下发之前完成那它就不可能出现在 pq2 里了 
            pq2.push(cur);
        }
    }

    rep(i,1,m){
        //n 和 m 别弄混了 
        cout<<ans[i].size()<<' ';

        if(ans[i].empty()==0){
            sort(ans[i].begin(),ans[i].end());
            //要排序，因为排序前是按照打印的先后顺序 

            for(ll j:ans[i]) cout<<j<<' ';
        }

        endl;
    }
}