最快的代码

#include<bits/stdc++.h>
#define N 100005
#define int long long
using namespace std;
int s[N];
struct Queue
{
	#define M 10000005
	int q[M],f=0,b=0;
	int front()
	{
		return q[f];
	}
	void pop()
	{
		f++;
	}
	void push(int x)
	{
		q[b++]=x;
	}
	int size()
	{
		return b-f;
	}
	#undef M
}q1,q2;
int read()
{
	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-48,s=getchar();
	return x*f;
}
signed main()
{
	int n;
	n=read();
	for(int i=1;i<=n;i++)
		s[read()]++;
	for(int i=1;i<=N;i++)
		while(s[i]--)
			q1.push(i);
	int ans=0;
	while(q1.size()+q2.size()>1)
	{
		int x=0;
		if(!q2.size() || q1.size() && q1.front()<q2.front())
			x+=q1.front(),q1.pop();
		else x+=q2.front(),q2.pop();
		if(!q2.size() || q1.size() && q1.front()<q2.front())
			x+=q1.front(),q1.pop();
		else x+=q2.front(),q2.pop();
		ans+=x;
		q2.push(x);
	}
	printf("%lld",ans);
	return 0;
}

解题思路

首先根据题面，能想到的贪心思路：越小的数参与的合并次数应该多些，越大的数参与合并的次数应该少些。下面简单证明一下。

假设有两堆果子重量分别为 $a,b$，且 $a>b$，设它们参与合并的次数分别为 $x,y$。如果 $x>y$，那么可以考虑将两堆果子调换，即参与合并的次数改为 $y,x$。那么前后两次的代价（只看这两堆果子）分别为 $ax+by$ 和 $ay+bx$。两式相减即为 $(a-b)(x-y)$，显然大于零，贪心策略成立。

用“小根堆”维护一下就好了，时间复杂度：$O(n^2)$。

代码：

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

int n, x, sum, ans;
priority_queue<int,vector<int>,greater<int> > q; //小根堆 

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> x;
		q.push(x); // 边读入编存 
	}
	// 思路：取出前两个数，合并后重新放入堆 
	while (q.size() > 1) // 在堆里还有1个的情况下均可合并果子 
	{
		sum += q.top();
		q.pop(); //出队 
		sum += q.top();
		q.pop(); // 再次出队		
		ans += sum; // 全部累加 
		q.push(sum);
		sum = 0; // 清空sum 
	}
	cout << ans << endl; // 输出ans即可 
	return 0;
}

交上去 30pts，开个 long long 得到 60pts，很显然，$O(n^2)$ 肯定会 TLE，开始考虑优化。

要把它化为线性，就必须找到其中的单调性。可以发现的，就是先合并的必定小于等于后合并的。定义先合并 $a_1,b_1$，后合并 $a_2,b_2$。因为是按照从小到大的顺序合并的，所以必定有 $a_1\le a_2,b_1\le b_2$，所以 $a_1+b_1\le a_2+b_2$。那我们就可以把没合并的与合并的分处于两个队列，一开始将初始的各堆桶排序，然后从小到大插入没合并的队列。然后在两个队列中取两次最小，两次的和再插入合并的队列并统计代价，直到只剩一堆输出。时间复杂度：$O(n)$。

注意数据：$1 \leq n \leq 10^7$，所以要用快读，不然一样 TLE 的。

代码：

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

const int N = 1e5 + 5, M = 1e7 + 5; // 注意数据范围！ 

long long w[M], k[N], n, ans;
queue<long long> q1, q2; // 把没合并的与合并的分处于两个队列

long long read() // 快读，不然会 TLE 
{
	long long x = 0;
	char s = getchar();
	while (s < '0' || s > '9') s = getchar();
	while (s >= '0' && s <= '9') x = x * 10 + s - '0', s = getchar();
	return x;
}

int main()
{
	n = read();
    for (int i = 0; i < n; i++) w[i] = read(), k[w[i]]++; // 桶排序 
    for (int i = 1; i < N; i++)
        for (int j = 1; j <= k[i]; j++)
        	q1.push(i); // 桶排序的结果导入队列 
    while (q1.size() + q2.size() > 1)
	{
    	long long x;
        if (q2.empty() || !q1.empty() && q1.front() < q2.front()) x = q1.front(), q1.pop(); // 这与下面的都是取最小，取两次
		else x = q2.front(), q2.pop();
		if (q2.empty() || !q1.empty() && q1.front() < q2.front()) x += q1.front(), q1.pop();
		else x += q2.front(), q2.pop();
		ans += x;
		q2.push(x);
    }
    cout << ans << endl; // 输出答案即可 
    return 0;
}