优先队列存答案怎么就不行了呢
查看原帖
优先队列存答案怎么就不行了呢
882193
Blue_Flower楼主2024/11/21 17:21

代码算法部分没换,换成 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;
}
2024/11/21 17:21
加载中...