做题记录整理数据结构1 P6033. [NOIP2004 提高组] 合并果子 加强版（2022/10/3）

P6033. [NOIP2004 提高组] 合并果子 加强版

老题新做型

里面最妙的就是用两个队列来代替一个堆，和蚯蚓那道题有异曲同工之妙

#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
ll ans;
int n,a,vis[100100];
queue<ll> q1,q2;
void read(int &x){ 
	int f=1;x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	x*=f;
}
inline ll cl() {
	if (q2.empty()||(!q1.empty()&&q1.front()<q2.front()))
	 {
		ll x=q1.front();
		q1.pop();
		return x;
	} 
	else 
	{
		ll x=q2.front();
		q2.pop();
		return x;
	}
}
int main()
{
	read(n);
	for1(i,1,n)
	   read(a),
		vis[a]++;
	for1(i,1,100005)
		for1(j,1,vis[i])
			q1.push(i);
	for1(i,1,n-1) 
	{
		ll x=cl();
		ll y=cl();
		ans+=x+y;
		q2.push(x+y);
	}
	printf("%lld",ans);
	return 0;
}