队列好题

step 1

用优先队列，每次从队头取最小的两个合并，但会超时

step 2

因为每次选的是最小的两堆石子合并，所以桶排一下，直接用队列即可。一个队列放没合并过的，一个队列放已经合并过的，显然他们是单增的

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long

namespace syr
{
	ll read () {
		char c;
		ll f = 1, x = 0;
		c = getchar();
		while (c<'0' || c>'9') {
			if (c=='-') f = -1;
			c = getchar();
		}
		while (c>='0' && c<='9') {
			x = (x<<3)+(x<<1)+c-'0';
			c = getchar();
		}
		return x*f;
	}
	void write (ll x) {
		if (x<0) {
			putchar('-');
			x = -x;
		}
		if (x>9) write(x/10);
		putchar(x%10+'0');
	}
	
	const ll N = 1e5+10;
	ll n, ans;
	ll a[N];
	queue <ll> q[3];
	ll solve () {
		if (q[1].empty()) {
			ll x = q[2].front();
			q[2].pop();
			return x;
		}
		if (q[2].empty()) {
			ll x = q[1].front();
			q[1].pop();
			return x;
		}
		ll x = q[1].front();
		ll y = q[2].front();
		if (x<y) q[1].pop();
		else q[2].pop();
		return min(x, y);
	}
	void work()
	{
//		freopen("c.in", "r", stdin);
		n = read();
		for (ll i=1; i<=n; i++) a[read()]++;
		for (ll i=1; i<N; i++) {
			while (a[i]) {
				a[i]--;
				q[1].push(i);
			}
		}
		for (ll i=1; i<n; i++) {
			ll x, y, id=0;
			if (q[1].empty()) id=2;
			else if (q[2].empty()) id=1;
			if (id) {
				x = q[id].front();
				q[id].pop();
				y = q[id].front();
				q[id].pop();
			}else {
				x = solve();
				y = solve();
			}
			q[2].push(x+y);
			ans += x+y;
		}
		write(ans);
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	syr::work();
	return 0;
}