代码算法部分没换,换成 vector 存答案最后再排序输出就过了,用优先队列存答案 70 pts Wa,有没有大佬解释一下。 代码如下:
#include<bits/stdc++.h>
#define N 400005
#define ll long long
using namespace std;
struct file
{
int t,s,id;
}a[N];
struct node
{
int num,w;
friend bool operator <(node x,node y)
{
if(x.w==y.w) return x.num > y.num;
return x.w > y.w;
}
};
int n,m;
priority_queue<int,vector<int>,greater<int> > q,ans[N];
priority_queue<node> p;
inline int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x;
}
inline bool cmp(file x,file y)
{
return x.t < y.t;
}
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i++){a[i].s=read();a[i].t=read();a[i].id=i;}
for(int i=1;i<=m;i++) q.push(i);
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
while(!p.empty())
{
node pos=p.top();
if(pos.w <= a[i].t)
{
p.pop();q.push(pos.num);
}
else break;
}
if(!q.empty())
{
int pos=q.top();q.pop();
ans[pos].push(a[i].id);
p.push(node{pos,a[i].t+a[i].s});
}
else
{
node pos=p.top();p.pop();
ans[pos.num].push(a[i].id);
p.push(node{pos.num,pos.w+a[i].s});
}
}
for(int i=1;i<=m;i++)
{
cout<<ans[i].size()<<" ";
while(!ans[i].empty())
{
cout<<ans[i].top()<<" ";
ans[i].pop();
}
puts("");
}
return 0;
}