本文同步于洛谷专栏，见 QAQ。

闲话：大样例以及 $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();}
    }

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

完整代码如下。

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N = 2e5 + 10;
namespace FastIO {
	char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++)
	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
	template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
	template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
}; using namespace FastIO;
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("");}
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solution::solve();
    return 0;
}

题解

锐评

不得不说作为一道模拟题它是非常好的，类似于廊桥分配。
但是谴责黑心大样例！！！

题意

对于每一个文件，选择一个编号最小以及等待时间最短的打印机进行打印。

40Pts TLE

使用一个优先队列存储每个节点信息，然后每次取队顶，对于每一次时间增加我们重新更新队列。
由于优先队列不支持直接修改，也没有迭代器，因此我们只能一个一个更新出队再进队，所以非常费时。

#include <bits/stdc++.h>
using namespace std;
#define maxn int(2e5)
#define _for(a,b,c) for(int i = a;i <= b;i+=c)
struct p{
	int nxt,id;
	bool operator < (const struct p &a) const{
		return nxt == a.nxt ? id > a.id : nxt > a.nxt;
	}
};
priority_queue<p> q;
struct wj{
	int s,t,id;
} w[maxn];
bool cmp(wj A,wj B){return A.t < B.t;}
int read(){
    int X=0,w=0; char c=0;
    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
    while(c>='0'&& c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
    return w? -X : X;
}
vector<int> ans[maxn+10];
int c1[maxn+10],c2[maxn+10];
signed main(){
	//freopen("print3.in","r",stdin);
	//freopen("print.txt","w",stdout);
	int n = read(),m = read();
	_for(1,n,1) w[i].s = read(),w[i].t = read(),w[i].id = i;
	sort(w+1,w+1+n,cmp);
	_for(1,m,1) q.push(p{0,i}); 
	_for(1,n,1){
		int tot = 0;
		while(!q.empty()){
			int tmp1 = q.top().nxt;
			tmp1 -= (w[i].t - w[i-1].t);
			if(tmp1 < 0) tmp1 = 0;
			int tmp2 = q.top().id;
			q.pop();
			c1[++tot] = tmp1,c2[tot] = tmp2;
		}
		for(int j = 1;j <= tot;j++){
			q.push((p){c1[j],c2[j]});
		}
		//printf("%d %d\n",q.top().nxt,q.top().id);
		ans[q.top().id].push_back(w[i].id);
		int tmp = q.top().nxt + w[i].s;
		int tmp2 = q.top().id;
		q.pop();
		q.push((p){tmp,tmp2}); 
	}
	_for(1,m,1){
		printf("%d ",ans[i].size());
		sort(ans[i].begin(),ans[i].end());
		for(int j = 0;j < ans[i].size();j++) printf("%d ",ans[i][j]);
		printf("\n");
	}
	return 0;
} 

About 60 Pts

这个原因各有吧。。。
至少我自己是没有考虑没有打印机空闲的情况。

正解

还是优先队列，但是这次变成了两个。
一个用于存储没有打印任务的打印机，一个存储有任务的打印机。
如果有打印机没有打印任务直接选择里面最小的。
否则，找到等待时间最小的那一个。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 200010;
#define int long long
int n,m;
struct node{int s,t,id;}a[maxn];
bool cmp(node &A,node &B){return A.t<B.t;}
struct print{
    int id,t;
    bool operator < (const print &x)const{
        return t==x.t ? id>x.id : t>x.t;
    }
};    
priority_queue <print> q;
priority_queue <int,vector<int>,greater<int> > v;
priority_queue <int,vector<int>,greater<int> > ans[maxn];
int read(){
    int X=0,w=0; char c=0;
    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
    while(c>='0'&& c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
    return w? -X : X;
}
signed main(){
    int n = read(),m = read();
    for(int i = 1;i <= n;i++) a[i].s = read(),a[i].t = read(),a[i].id=i;
    sort(a+1,a+1+n,cmp);
    for(int i = 1;i <= m;i++) v.push(i);
    for(int i = 1;i <= n;i++){
        while(q.size() && q.top().t <= a[i].t) v.push(q.top().id),q.pop();
        if(v.empty()) ans[q.top().id].push(a[i].id),q.push({q.top().id,q.top().t+a[i].s}),q.pop();
        else ans[v.top()].push(a[i].id),q.push({v.top(),a[i].s+a[i].t}),v.pop();
    }
    for(int i = 1;i <= m;i++){
        printf("%d ",ans[i].size());
        for(int j = 0;j < ans[i].size();j++){
            while(!ans[i].empty()){
                printf("%d ",ans[i].top());
                ans[i].pop();
            }      
        }
        printf("\n");
    }
    if(1+1==3) cout << "I_I_A_K_I_O_I!!!!";
    return 0;
}