这道题我先是写了个贪心，然后TLE了……

具体思路就是每次排序都取前面两个元素进行合并，然后把第一个元素加到第二个元素，再从第二个元素开始排序，循环n-1次

附上50分代码：

#include <bits/stdc++.h>
using namespace std;
int a[10009];
int n;
int sum = 0;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    int t = n-1;
    int k = 1;
    while (t--)
    {
        sort(a + k, a + n + 1);   
        sum += (a[k] + a[k+1]);
        a[k+1] += a[k];a[k] = 0;
        k += 1;      
    }
    cout << sum << endl;
    return 0;
}

那当我们发现超时只有5~10ms时，就可以开始优化 比如快读快写

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();
	int x=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48,ch=getchar();}
	return x*f;
}
inline void write(int x)
{
	if(x<0) x=-x,putchar('-');
	if(x<10) putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}
int a[10009];
int n;
int sum = 0;
int main()
{
    n=read();
    for (int i = 1; i <= n; i++)a[i]=read();
    int t = n-1;
    int k = 1;
    while (t--)
    {
        sort(a + k, a + n + 1);   
        sum += (a[k] + a[k+1]);
        a[k+1] += a[k];a[k] = 0;
        k += 1;      
    }
    write(sum);
    return 0;
}

然后结果还是T了……没事，上火车头（O2 O3）

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();
	int x=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48,ch=getchar();}
	return x*f;
}
inline void write(int x)
{
	if(x<0) x=-x,putchar('-');
	if(x<10) putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}
int a[10009];
int n;
int sum = 0;
int main()
{
    n=read();
    for (int i = 1; i <= n; i++)a[i]=read();
    int t = n-1;
    int k = 1;
    while (t--)
    {
        sort(a + k, a + n + 1);   
        sum += (a[k] + a[k+1]);
        a[k+1] += a[k];a[k] = 0;
        k += 1;      
    }
    write(sum);
    return 0;
}

愣是把这道题卡过去了

玩归玩，正解还是得上一份（哈夫曼+优先队列）：

#include <bits/stdc++.h>
#define cin read()
using namespace std;
inline int read(){
	char ch=getchar();
	int x=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48,ch=getchar();}
	return x*f;
}
inline void write(int x)
{
	if(x<0) x=-x,putchar('-');
	if(x<10) putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}
priority_queue<int, vector<int>, greater<int> > heap;
int main() {
	int n=cin;

	while(n--) {
		int x=cin;
		heap.push(x);
	}
	int res=0;
	while(heap.size()>1) {
		int a=heap.top();	heap.pop();
		int b=heap.top();	heap.pop();
		res += a + b;
		heap.push(a+b);
	}
	write(res);
	return 0;
}

Orz