队列好题

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;
}

先桶排，然后弄俩队列

然后把所有的数放到第一个队列里面

然后每次选两个队列里面最小的两个数，把他俩合并扔到第二个队列里面，咱俩数合并完的数是显然单增的，所以第二个队列也是单增的。

这样就做完了

code

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

bool mlest;

double tlest, tleed;

inline long long R(){
	long long x = 0, f = 1; char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}

inline void W(long long x){
	if(x < 0) {putchar('-'); x = -x;}
	if(x > 9) W(x/10); putchar(x%10+'0');
}

const long long N = 1e5 + 1;

long long n, a[N];

queue<long long> q1, q2;

inline void read(){
	n = R();
	for(long long i = 1;i <= n; i++){
		long long x = R();
		a[x]++;
	}
	for(long long i = 1;i <= 100000; i++){
		while(a[i]){
			q1.push(i);
			a[i]--;
		}
	}
}

inline void init(){

}

inline void compute(){
	long long ans = 0;
	for(long long i = 1;i < n; i++){
		long long x, y;
		if((q1.size() && q2.size() && q1.front() < q2.front()) || (q1.size() && !q2.size())) {
			x = q1.front();
			q1.pop();
		}
		else{
			x = q2.front();
			q2.pop();
		}
		if((q1.size() && q2.size() && q1.front() < q2.front()) || (q1.size() && !q2.size())) {
			y = q1.front();
			q1.pop();
		}
		else{
			y = q2.front();
			q2.pop();
		}
		ans += x + y;
		q2.push(x+y);
	}
	W(ans);
}

inline void clear(){

}

void run(){read(); init(); compute(); clear();}

bool mleed;

void wa(){cout << '\n' << tleed - tlest << "ms\n" << (&mleed-&mlest-1)/1024.0/1024.0 << "MB\n";}

void fre(string s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

int main(){
//	fre("");
	tlest = clock();
	run();
	tleed = clock();
//	wa();
	return 0;
}

还是推荐证明一下贪心单调性的。

注意两个队列写法太复杂的话会像我一样人傻常数大不开 O2 被卡常。