题目大意

给定打印任务的开始时间和持续时间，求每个打印机打印的任务数量和编号（会优先选择编号小的打印机）。

思路分析

我们开两个优先队列，分别维护当前空闲打印机（按照编号为第一关键字）；和当前有任务打印机（按照任务结束时间为第一关键字，编号为第二关键字）。

注意：需要开 longlong 的变量!

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;

int n,m;

vector <int> pr[N];

struct node{
    int ed;
    int idx;
};

struct node1{
    int ed;
    int idx;
};

struct fil{
    int st;
    int vl;
    int idx;
}tx[N];

bool cmp(const fil &x,const fil &y){
    return x.st<y.st;
}

priority_queue <node> q;
priority_queue <node1> q_u;

bool operator <(const node &x,const node &y){
    return x.idx>y.idx;
} 

bool operator <(const node1 &x,const node1 &y){
    if(x.ed==y.ed)return x.idx>y.idx;
    return x.ed>y.ed;
}

signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&tx[i].vl,&tx[i].st);
        tx[i].idx=i;
    }
    sort(tx+1,tx+1+n,cmp);
    for(int i=1;i<=m;i++)q.push((node){0,i});
    for(int i=1;i<=n;i++){
        while(q_u.size()&&q_u.top().ed<=tx[i].st){
            node1 k=q_u.top();
            node k1={k.ed,k.idx};
            q_u.pop();
            q.push(k1);
        }
        if(q.empty()){
            node1 k=q_u.top();
            node k1={k.ed,k.idx};
            q_u.pop();
            q.push(k1);
        }
        node p=q.top();
        q.pop();
        pr[p.idx].push_back(tx[i].idx);
        p.ed=max(p.ed+tx[i].vl,tx[i].st+tx[i].vl);
        node1 o={p.ed,p.idx};
        q_u.push(o);
    }
    for(int i=1;i<=m;i++){
        sort(pr[i].begin(),pr[i].end());
        printf("%d",pr[i].size());
        for(int j=0;j<pr[i].size();j++)printf(" %lld",pr[i][j]);
        printf("\n");
    }
    return 0;
}