使用优先队列即可快速解决此题
#include<iostream>
#include<queue>
#include<vector>

using namespace std;

struct cmp{

bool operator ()(long &a,long &b) const
{
return a > b;
}

};

int main()
{
priority_queue<long,vector<long>,cmp> qp;
int n,i;
long sum = 0,temp;
cin>>n;
for(i = 0;i < n;i++)
{
cin>>temp;
qp.push(temp);
}
while(qp.size() > 1)
{
long t1,t2;
t1 = qp.top();
qp.pop();
t2 = qp.top();
qp.pop();
t1 = t1 + t2;
sum += t1;
qp.push(t1);
}
cout<<sum;
return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
int gg[20001];
int main(int argc, char** argv)
{
long long tt=0;
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>gg[i];
}
for(int j=1;j<n;j++)
{
sort(gg+j,gg+1+n);
tt=tt+gg[j]+gg[j+1];
gg[j+1]=gg[j]+gg[j+1];
}
cout<<tt;
return 0;
}

每次取最小的两个数求和，然后塞回去。
这不明摆着让你用堆去维护吗？我在想数据规模再大点会不会搞死你们这帮每次都要重新排序的XD

import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    static FileReader fr;

    static int n;
    static int[] heap;
    static int count;
    
    public static Scanner getInput() {
        return new Scanner(System.in);
    }

    
//  public static Scanner getInput() throws IOException {
//      File f = new File("input.txt");
//      fr = new FileReader(f);
//      Scanner sc = new Scanner(fr);
//      return sc;
//  }

    private static void maintaince() {
        int index = 1;
        while (true) {
            int value = heap[index];
            int minValue = value;
            if (index * 2 + 1 <= count) {
                int lValue = heap[index*2];
                int rValue = heap[index*2+1];
                minValue = Math.min(lValue, minValue);
                minValue = Math.min(rValue, minValue);
                if (minValue == lValue) {
                    int tmp = heap[index];
                    heap[index] = heap[index*2];
                    heap[index*2] = tmp;
                    index = index * 2;
                }else if (minValue == rValue) {
                    int tmp = heap[index];
                    heap[index] = heap[index*2 + 1];
                    heap[index*2 + 1] = tmp;
                    index = index * 2 + 1;
                }else {
                    break;
                }
            }else if (index * 2 == count) {
                int lValue = heap[index*2];
                minValue = Math.min(lValue, minValue);
                if (minValue == lValue) {
                    int tmp = heap[index];
                    heap[index] = heap[index*2];
                    heap[index*2] = tmp;
                    index = index * 2;
                }else {
                    break;
                }
            }else {
                break;
            }
        }
    }

    private static void maintaince2() {
        int index = count;
        while (index > 1) {
            int value = heap[index];
            int rootValue = heap[index/2];
            if (rootValue > value) {
                int tmp = heap[index];
                heap[index] = heap[index/2];
                heap[index/2] = tmp;
                index = index / 2;
            }else {
                break;
            }
        }
    }
    
    public static void input() throws IOException {
        Scanner sc = getInput();

        n = sc.nextInt();
        heap = new int[n+1];
        for (int i = 0; i < n; i++) {
            int value = sc.nextInt();
            addValue(value);
        }
        
        if (fr != null) {
            fr.close();
        }
    }
    
    private static int getMin() {
        int min = heap[1];
        heap[1] = heap[count];
        count--;
        maintaince();
        return min;
    }
    
    private static void addValue(int value) {
        count++;
        heap[count] = value;
        maintaince2();
    }

    public static int algorithm() {
        int result = 0;
        while (count > 1) {
            int min1 = getMin();
            int min2 = getMin();
            int neo = min1 + min2;
            result += neo;
            addValue(neo);
        }
        return result;
    }
        
    public static void output(int result) {
        System.out.println(result);
    }

    public static void main(String args[]) throws IOException {
        input();
        int result = algorithm();
        output(result);
    }

}

用set容器自动排序的特点可以实现

#include<cstdio>
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
multiset<long long>aa;
int main(){
long long n,i,a,b,c,sum=0;
multiset<long long>::iterator it;
cin>>n;
for(i=1;i<=n;i++) {scanf("%lld",&a); aa.insert(a);}
while(aa.size()!=1){
it=aa.begin();
sum+=*it;
b=*it;
aa.erase(it);
it=aa.begin();
c=*it;
sum+=c;
aa.erase(it);
aa.insert(b+c);

}
printf("%lld",sum);
return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int s=0;
for(int i=0;i<n-1;i++){
sort(a,a+n-i);
a[0]=a[0]+a[1];
s+=a[0];
for(int k=1;k<n;k++)
a[k]=a[k+1];
}
cout<<s;
}

#include<stdio.h>
long long a,b,c=0;
int main()
{
scanf("%d",&a);
for(int z=1;z<=a;z++)
{
scanf("%d",&b);
c=b+c+c;
}
printf("%d ",c);
return 0;
}

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Queue<Integer> fruit = new PriorityQueue<Integer>();
        for(int i = 0;i < n;i ++){
            fruit.add(scanner.nextInt());
        }
        scanner.close();
        
        int total = 0;
        while(fruit.size()>1){
            int sum = fruit.poll() + fruit.poll();
            fruit.add(sum);
            total += sum;
        }
        System.out.println(total);
    }
}

分享下堆的做法
get()是取出小根堆的根节点
put()是在堆中加入一个元素
效率很高

状态 耗时 内存占用

#1 Accepted 12ms 364.0 KiB
#2 Accepted 3ms 384.0 KiB
#3 Accepted 4ms 368.0 KiB
#4 Accepted 4ms 384.0 KiB
#5 Accepted 7ms 360.0 KiB
#6 Accepted 8ms 376.0 KiB
#7 Accepted 7ms 364.0 KiB
#8 Accepted 7ms 372.0 KiB
#9 Accepted 4ms 384.0 KiB
#10 Accepted 5ms 372.0 KiB

#include<bits/stdc++.h>
int a[20005],len;
using namespace std;
int get()
{
    int min,now,son,le,ri,t;
    min=a[1];
    a[1]=a[len];
    a[len]=0;
    len--;
    now=1;
    while(now*2<=len)
    {
        le=now*2;
        ri=now*2+1;
        if (ri>len)
            son=le;
        else
        {   
            if (a[le]<a[ri])
                son=le;
            else
                son=ri;
        }   
        if (a[now]>a[son])
        {
            t=a[now];
            a[now]=a[son];
            a[son]=t;
            now=son;
        }
        else
            break;
    }
    return min;
}
void put(int x)
{
    int now,fa,t;
    len++;
    a[len]=x;
    now=len;
    fa=now/2;
    while (now!=1)
    {
        if (a[now]<a[fa])
        {
            t=a[now];
            a[now]=a[fa];
            a[fa]=t;
            now=fa;
            fa=now/2;
        }
        else
            break;
    }
}
int main()
{
    int n,ans;
    int i,j,tmp,x,y;
    cin>>n;
    len=1;
    ans=0;
    cin>>a[1];
    for(i=2;i<=n;i++)
    {   
        cin>>tmp;
        put(tmp);
    }
    while (len>1)
    {
        x=get();
        y=get();
        ans=ans+x+y;
        put(x+y);
    }
    cout<<ans;
    return 0;
}

想了很久，冒泡排序两次去找最小值和次小值。
用代码空间复杂度换取时间和内存的优势。
记录详情
Accepted

状态 耗时 内存占用

#1 Accepted 324ms 372.0 KiB
#2 Accepted 3ms 360.0 KiB
#3 Accepted 5ms 352.0 KiB
#4 Accepted 9ms 356.0 KiB
#5 Accepted 66ms 384.0 KiB
#6 Accepted 116ms 372.0 KiB
#7 Accepted 279ms 460.0 KiB
#8 Accepted 329ms 256.0 KiB
#9 Accepted 206ms 356.0 KiB
#10 Accepted 325ms 340.0 KiB
代码
#include<iostream>
using namespace std;
#include<algorithm>
int sortNum;
int num[10000] = { 0 };
int AsmMinNum = 0;
int calMinEx()
{
for (int i = 0; i<sortNum - 1; i++)
{
for (int j = 1; j <= 2; j++)
{
if (i == 0) continue;
for (int k = sortNum -1; k > 0; k--)
{
if (num[k] == 0) continue;
if (num[k - 1] == 0)
{
num[k - 1] = num[k];
num[k] = 0;
}
else if (num[k] < num[k - 1])
{
int temp = num[k];
num[k] = num[k - 1];
num[k - 1] = temp;
}
}
}
AsmMinNum += num[0] + num[1];
num[1] = num[0] + num[1];
num[0] = 0;
}
return AsmMinNum;
}
int main()
{
cin >> sortNum;
for (int i = 0; i<sortNum; i++) cin >> num[i];
sort(num, num + sortNum);
cout << calMinEx() << endl;
return 0;
}
分数100总耗时1667ms峰值内存460.0 KiB

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

void least_two(vector<long long> &v);

int main()
{
vector<long long> v;
int num;
cin >> num;
for (int i = 0; i < num; i++)
{
long long temp;
cin >> temp;
v.push_back(temp);
}

least_two(v);

long long re = 0;

while (v.size()>1)
{
v[1] += v[0];
re += v[1];
v.erase(v.begin());
least_two(v);
}

cout << re;

system("pause");
return 0;
}

void least_two(vector<long long> &v)
{
for (unsigned int i = 0; i < v.size(); i++)
{
if (v[0] > v[i])
{
long long temp = v[0];
v[0] = v[i];
v[i] = temp;
}
}
for (unsigned int i = 1; i < v.size(); i++)
{
if (v[1] > v[i])
{
long long temp = v[1];
v[1] = v[i];
v[i] = temp;
}
}
}

Python code

import heapq


N = input()
vals = map(int, raw_input().split())
ans = 0

heapq.heapify(vals)
while len(vals) > 1:
    cur_cost = sum([heapq.heappop(vals) for i in (0, 1)])
    ans += cur_cost
    heapq.heappush(vals, cur_cost)

print ans

import bisect

n = raw_input()
a = raw_input().split()
a = sorted([int(i) for i in a])
s = 0
while len(a) > 1:
x = a.pop(0) + a.pop(0)
bisect.insort(a, x)
s = s + x
print s

本来想每次加完都排一次，结果运行时间超出了。。。只好插入排序
#include<stdio.h>
void px(long int k,long int n,long int g[])//从小到大排序
{
for(int i=k;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
if(g[i]>g[j])
{
g[0]=g[i];g[i]=g[j];g[j]=g[0];

}
}
}
int main()
{
long int g[10000]={0},n;
long int sum=0;
scanf("%ld",&n);
for(int i=1;i<=n;i++)
{
scanf("%ld",&g[i]);
}
px(1,n,g);
for(int k=2;k<=n;k++)
{
g[k]=g[k-1]+g[k];
sum+=g[k];
if(g[k]>g[k+1])
{
for(int i=k;i<=n-1;i++)//将g[k]插入到合适位置
{
if(g[i]<g[i+1])break;
g[0]=g[i];g[i]=g[i+1];g[i+1]=g[0];
}
}
}
printf("%ld",sum);
return 0;
}

//优化了一点点
#include <iostream>
using namespace std;

int main(int argc, char const *argv[])
{
std::ios_base::sync_with_stdio(false);
int n,min_phy = 0;
int fruit[10001];
cin>>n;
for(int i = 0; i < n; i++) {
cin>>fruit[i];
}
int fmin = fruit[0] > fruit[1]? 1 : 0;//最小值
int smin = fruit[1] <= fruit[0]? 0 : 1;//次小值
int pos = 0;
for(int i = 1; i < n; i++) {
for(int j = pos; j < n; j++) {//每次从pos开始搜索而不是从头
if(fruit[j] < fruit[fmin]) {
smin = fmin;
fmin = j;
}
else if(fruit[j] < fruit[smin] && j != fmin)
smin = j;
}
min_phy += fruit[fmin] + fruit[smin];
fruit[fmin] += fruit[smin];
swap(fruit[smin],fruit[pos++]);
fmin = fruit[pos] > fruit[pos+1]? pos+1 : pos;
smin = fruit[pos] > fruit[pos+1]? pos : pos+1;
}
cout << min_phy;
return 0;
}

再发个简单的优先队列
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> >p;//小的优先出的
int n;
int a,sum;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a;
p.push(a);
}
while(p.size()!=1)
{
int d=p.top(); p.pop();
int b=p.top(); p.pop();
int c=d+b; p.push(c);
sum+=c;
}
cout<<sum;
return 0;
}

没错此题是裸题
就是优先队列
而已
。

#include<iostream>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int tmp;
cin>>tmp;
q.push(tmp);    
}   
int ans=0;
for(int i=1;i<n;i++)
{
    int x=q.top();
    q.pop();
    int y=q.top();
    q.pop();
    int tmp2=x+y;
    ans+=tmp2;
    q.push(tmp2);
    
}
cout<<ans;

    
}    

#include<bits/stdc++.h>
using namespace std;
int n,ans,k,maxn;
int num[10008],sum[10008];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>num[i];
num[n+1]=0;
sort(num+1,num+1+n);
while(1)
{
int flag=0;
ans=num[1]+num[2];
sum[k]=ans;
if(k==n-1)
{
for(int i=0;i<k;i++)
maxn+=sum[i];
cout<<maxn;
return 0;
}
for(int i=3;i<=n-k;i++)
{
if(ans>num[i])
num[i-2]=num[i];
else
{
flag=1;
num[i-2]=ans;
for(int j=i-1;j<=n-k;j++)
num[j]=num[j+1];
break;
}
}
if(!flag) num[n-k-1]=ans;
k++;
}
return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,ans,k,maxn;
int num[10008],sum[10008];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>num[i];
num[n+1]=0;
sort(num+1,num+1+n);
while(1)
{
int flag=0;
ans=num[1]+num[2];
sum[k]=ans;
if(k==n-1)
{
for(int i=0;i<k;i++)
maxn+=sum[i];
cout<<maxn;
return 0;
}
for(int i=3;i<=n-k;i++)
{
if(ans>num[i])
num[i-2]=num[i];
else
{
flag=1;
num[i-2]=ans;
for(int j=i-1;j<=n-k;j++)
num[j]=num[j+1];
break;
}
}
if(!flag) num[n-k-1]=ans;
k++;
}
return 0;
}

没看到有dalao发优先队列，我就补一个优先队列的做法 (｡˘•ε•˘｡)
（还有，这题直接sort会TLE……）

#include<iostream>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;    
int n,x,ans=0,tmp=0;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        q.push(x);    
    }
    for(int i=1;i<=n-1;i++)
    {
        tmp=q.top();    
        q.pop();
        tmp=tmp+q.top();    
        q.pop();
        q.push(tmp);          
        ans=ans+tmp;         
    }
    cout<<ans;       
    return 0;
}

数组模拟队列

#include<bits/stdc++.h>
using namespace std;
int a[20001],b[20001];
int main()
{
    int n,al=1,bl=1,br=1,ans=0;
    memset(a,0x3f,sizeof(a));
    memset(b,0x3f,sizeof(b));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    for(int i=1;i<n;i++)
    {
        if(a[al+1]<=b[bl]&&a[al]+a[al+1]<=b[bl]+b[bl+1])
        {
            b[br]=a[al]+a[al+1];
            ans+=b[br];
            al+=2;
            br++;
        }
        else if(a[al+1]>=b[bl]&&a[al]<=b[bl+1])
        {
            b[br]=a[al]+b[bl];
            ans+=b[br];
            al++;
            bl++;
            br++;
        }
        else
        {
            b[br]=b[bl]+b[bl+1];
            ans+=b[br];
            bl+=2;
            br++;
        }
    }
    printf("%d",ans);
    return 0;
}