社区讨论

qwq萌新求教

P2073送花参与者 1已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi7x3a8s
此快照首次捕获于
2025/11/21 05:02
4 个月前
此快照最后确认于
2025/11/21 05:02
4 个月前
查看原帖
用优先队列得了10ptsqwq 死了
CPP
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=1000010;
priority_queue<int>q1;
priority_queue<int,vector<int>,greater<int> >q2;
queue<int>q;
long long ans=0,ans1=0;
int vis[maxn],cost[maxn],vis2[maxn],w,c;
inline void read(int &x){
	static char rc;static int flag;
	rc=getchar();flag=1;x=0;
	while(rc<'0'||rc>'9')
	  flag=(rc=='-'?-1:1),rc=getchar();
	while(rc<='9'&&rc>='0')
	  x=x*10+rc-'0',rc=getchar();
	x=x*flag;
}
int main(){
	int k;read(k);
	while(k!=-1){
		if(k==1){
			read(w),read(c);
			if(!vis[c]){
				q1.push(c),q2.push(c);
				cost[c]=w;
			}
		}
		if(k==3){
			if(q2.empty())continue;
			int h=q2.top();
			vis[h]=0;cost[h]=0;
			q2.pop();
		}
		if(k==2){
			if(q1.empty())continue;
			int h=q1.top();
			vis[h]=0;cost[h]=0;
			q1.pop();
		}
		read(k);
	}
	while(!q1.empty()){
		int h=q1.top();
		vis2[h]=1;
		q1.pop();
	}
	while(!q2.empty()){
		int h=q2.top();
		if(vis2[h]==1)q.push(h);
		q2.pop();
	}
	while(!q.empty()){
		int h=q.front();
		ans+=cost[h];
		ans1+=h;
		q.pop();
	}
	cout<<ans<<' '<<ans1;
}
还极其诡异的T了? (复杂度好像是常熟比较大的O(n)吧qwq,为啥慢的飞起)

回复

2 条回复,欢迎继续交流。

正在加载回复...