#include<stdio.h>
int main()
{
    int n, a[10000];
    scanf("%d", &n);
    int i, min1, min2;
    int sum = 0;
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    min1 = 0, min2 = 1;                   //其实初始化min1和min2是0或者1都无所谓
    int t = n - 1;                        //注意到这里要复制一个n
    while (t--)                           //是先判断t，再自减，故上一行需要n-1
    {
        for (i = 0; i < n; i++)           //找到最小值和次小值的下标，无论min1和min2值如何，都可以找到最小和次小
        {
            if (a[i] < a[min1])
            {
                min2 = min1;
                min1 = i;
            }
            else if (a[i] >= a[min1] && a[i] < a[min2] && i != min1)
                min2 = i;
        }
        sum += a[min1] + a[min2];
        a[min2] += a[min1];           //把次小值更新为和
        a[min1] = 99999999;           //把最小值标记为一个足够大的值
    }
    printf("%d", sum);
    return 0;
}

首先看到各位大佬用的都是堆或桶我也就放心了
当然我做这道题的思路也是堆

但是,简单的介绍堆并不是我写这道题的目的

我写这篇题解，是为了让各位了解一下大家平时很少注意的C++的某个方面
发掘更多新玩法

把你们从算法的深渊拉出来

—————————————分割线———————————————

————————————正文开始———————————————

————————————此篇为C++福利——————————

第一部分
设想一下，某一天，当你兴致勃勃的在vijos里刷题时，看到了一道叫“合并果子”的题，你不屑地扫了一遍题目，心想着这种模板题也好意思入选提高组。迅速用小根堆将它AC后，却对堆产生了浓厚兴趣，便又找来一道与堆有关的题，惊讶发现该题的数据long long装不下，于是又写了一篇高精，但是在结合两者时却死活都结合不了，最后关掉电脑，生无可恋。

换一个场景，很多人都用过，至少接触过C++的STL库，那么应该就很熟悉形似这样的东西

priority_queue < int, vector<int>, greater<int> >;
vector < long long >;
queue <double >;

一些细心的人可能就会发现，在<>简直可以装下任何数据类型，那么C++，到底是如何实现这种操作的呢？

—————————分割线——————————

—————————分割线——————————

—————————分割线——————————

第二部分
我们回到第一个设想，你在写了一篇堆模板后，为了让它能够支持不同数据类型，对代码进行了这样的改动

typedef item int;
class heap{
    private:
        item h[1001];
        int len;
    public:
        heap();
        void push(item const &);
        void pop();
}

这样就可以针对不同数据类型，运用不同的堆

typedef item long long;
class heap{
    private:
        item h[1001];
        int len;
    public:
        heap();
        void push(item const &);
        void pop();
}
typedef item string;
class heap{
    private:
        item h[1001];
        int len;
    public:
        heap();
        void push(item const &);
        void pop();
}

但这样却有两个致命的缺陷，那就是每次使用，都得改一下头文件，并且不能同时存在两个不同类型的堆。那么应该怎样做呢？你不禁陷入了沉思。

第三部分
聪明的你当然知道如何使用网络来使自己的生活更加便利，于是你在“百度一下”中打出了

priority_queue < int, vector<int>, greater<int> >
并按下了回车，结果跳出来满屏的“容器”啊，“CSDN博客”啊之类的，让你心烦意燥，分分钟原地爆炸。或是瞅着顺眼的点了一篇，耐着性子看完，最后学到了NOTHING。

但是，一个词语突然从你眼前闪过，这个词语仿佛有着魔力，使你的视线一下子聚焦在了它身上，你的脑中仿佛浮现出了什么，又仿佛没有。

“类模板”
你轻轻地念叨着这词。

第四部分
类模板，模板的类型参数由关键字class 或关键字typename 及其后的标识符构成。在模板参数表中关键字class 和typename 的意义相同。(在标准C++之前关键字typename 没有被支持 ，把这个关键字加入到C++中的原因是因为有时必须要靠它来指导编译器解释模板定义。)，是对一批仅仅成员数据类型不同的类的抽象，程序员只要为这一批类所组成的整个类家族创建一个类模板，给出一套程序代码，就可以用来生成多种具体的类，(这类可以看作是类模板的实例)，从而大大提高编程的效率。————360百科
我们举个列子：

template<typename item>
class smallest_heap{
    private:
        item heap[10001];
        int len;
    public:
        smallest_heap();
        void push(item const &);
        void pop();
        item top();
        int size();
        bool empty();
        
};

其中第一排的

template<typename item>

就是关键，它指出接下来声明的某个类是模板，也就是部分数据类型不确定，暂且将这种数据类型叫做

item

而方法（也就是成员函数），相信各位大佬都会写。但是，要注意，在操作时，有一些不同指出

template<typename item>
smallest_heap<item>::smallest_heap(){
    len=0;
    memset(heap,0,sizeof(heap));
}

template<typename item>
void smallest_heap<item>::push(item const &n){
    heap[++len]=n;
    int son=len,father=son/2;
    while(heap[son]<heap[father] && father>=1){
        swap(heap[son],heap[father]);
        son=father,father=son/2;
    }
}

template<typename item>
void smallest_heap<item>::pop(){
    swap(heap[1],heap[len]);
    heap[len--]=0;
    int father=1,son=2;
    while(son<=len){
        if(son<len && heap[son]>heap[son+1]) son++;
        if(heap[father]>heap[son]){
            swap(heap[father],heap[son]);
            father=son,son=father*2;
        }else break;
    }
}

template<typename item>
item smallest_heap<item>::top(){
    return heap[1];
}

template<typename item>
int smallest_heap<item>::size(){
    return len;
}

template<typename item>
bool smallest_heap<item>::empty(){
    return len;
}

在每个方法前，都加了一排

template<typename item>
这是因为类的数据类型不确定，自然方法数据类型也不确定，所以用

item
来替代。并且在声明方法所属域时，也不是

smallest_heap::smallest_heap()
而是

smallest_heap<item>::smallest_heap()
最后送上AC代码以及小根堆，大根堆模板一份

> 番外
AC代码

#include<iostream>
#include<cstring>
using namespace std;

template<typename item>
class smallest_heap{
    private:
        item heap[10001];
        int len;
    public:
        smallest_heap();
        void push(item const &);
        void pop();
        item top();
        int size();
        bool empty();
        
};

template<typename item>
smallest_heap<item>::smallest_heap(){
    len=0;
    memset(heap,0,sizeof(heap));
}

template<typename item>
void smallest_heap<item>::push(item const &n){
    heap[++len]=n;
    int son=len,father=son/2;
    while(heap[son]<heap[father] && father>=1){
        swap(heap[son],heap[father]);
        son=father,father=son/2;
    }
}

template<typename item>
void smallest_heap<item>::pop(){
    swap(heap[1],heap[len]);
    heap[len--]=0;
    int father=1,son=2;
    while(son<=len){
        if(son<len && heap[son]>heap[son+1]) son++;
        if(heap[father]>heap[son]){
            swap(heap[father],heap[son]);
            father=son,son=father*2;
        }else break;
    }
}

template<typename item>
item smallest_heap<item>::top(){
    return heap[1];
}

template<typename item>
int smallest_heap<item>::size(){
    return len;
}

template<typename item>
bool smallest_heap<item>::empty(){
    return len;
}


smallest_heap<int> h;
int n,ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        h.push(a);
    }
    while(h.size()>1){
        int x=h.top(); h.pop();
        int y=h.top(); h.pop();
        h.push(x+y);
        ans+=x+y;
    }
    cout<<ans;
    return 0;
}
小根堆

#include<cstring>

template<typename item>
class smallest_heap{
    private:
        item heap[10001];
        int len;
    public:
        smallest_heap();
        void push(item const &);
        void pop();
        item top();
        int size();
        bool empty();
        
};

template<typename item>
smallest_heap<item>::smallest_heap(){
    len=0;
    memset(heap,0,sizeof(heap));
}

template<typename item>
void smallest_heap<item>::push(item const &n){
    heap[++len]=n;
    int son=len,father=son/2;
    while(heap[son]<heap[father] && father>=1){
        swap(heap[son],heap[father]);
        son=father,father=son/2;
    }
}

template<typename item>
void smallest_heap<item>::pop(){
    swap(heap[1],heap[len]);
    heap[len--]=0;
    int father=1,son=2;
    while(son<=len){
        if(son<len && heap[son]>heap[son+1]) son++;
        if(heap[father]>heap[son]){
            swap(heap[father],heap[son]);
            father=son,son=father*2;
        }else break;
    }
}

template<typename item>
item smallest_heap<item>::top(){
    return heap[1];
}

template<typename item>
int smallest_heap<item>::size(){
    return len;
}

template<typename item>
bool smallest_heap<item>::empty(){
    return len;
}
大根堆

#include<cstring>

template<typename item>
class largest_heap{
    private:
        item heap[10001];
        int len;
    public:
        largest_heap();
        void push(item const &);
        void pop();
        item top();
        int size();
        bool empty();
        
};

template<typename item>
largest_heap<item>::largest_heap(){
    len=0;
    memset(heap,0,sizeof(heap));
}

template<typename item>
void largest_heap<item>::push(item const &n){
    heap[++len]=n;
    int son=len,father=son/2;
    while(heap[son]>heap[father] && father>=1){
        swap(heap[son],heap[father]);
        son=father,father=son/2;
    }
}

template<typename item>
void largest_heap<item>::pop(){
    swap(heap[1],heap[len]);
    heap[len--]=0;
    int father=1,son=2;
    while(son<=len){
        if(son<len && heap[son]<heap[son+1]) son++;
        if(heap[father]<heap[son]){
            swap(heap[father],heap[son]);
            father=son,son=father*2;
        }else break;
    }
}

template<typename item>
item largest_heap<item>::top(){
    return heap[1];
}

template<typename item>
int largest_heap<item>::size(){
    return len;
}

template<typename item>
bool largest_heap<item>::empty(){
    return len;

同时也可以支持自己编写的类，但须提供“<”或“>”的运算符重载，例如

class T{
    private:
        int a;
    public:
        bool operator<(T const &type){
            return a<type.a;
        }
};
smallest_heap<T> heap;

最后的总结
我们现在所运用的C++，只是它的冰山一角，如果有与我同样爱好C++的，对运算符重载，lambda函数，类继承，函数重载，虚方法等感兴趣的，可以私信我，一起进步！

番外中的番外
推荐一个网站和一本书

C语言中文网 c.biancheng.net

《C++ Primer Plus》

----毕竟萌新，文笔不好，请多多包容

不难发现此题的最优策略就是：每次取出最小的两个数，相加，放入序列，重复此操作。

那么如何维护每次最小的两个数呢？这里首先排除掉sort，因为一次sort并不满足上述

每次取出最小的两个数

如果每次操作都是用一次sort的话，时间复杂度是巨大的，故不能AC

那有什么办法能在 \( O(n) \) 的时间复杂度之内，处理完维护每次取出最小的两个数呢？

既然静态维护无法，就动态维护

动态维护，最小……

小根堆！！！

于是就有了水代码了

ACcode

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

priority_queue <int, vector <int>, greater <int>> q; 

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int num; cin >> num;
        q.push(num);
    }
    int ans = 0;
    while (q.size() > 1)
    {
        int t1 = q.top();
        q.pop();
        int t2 = q.top();
        q.pop();
        ans += t1 + t2;
        q.push(t1 + t2);
    }
    cout << ans << endl;
    return 0;
}

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

int k,x,num,n1,n2,a1[30001],a2[30001],t[20001],w,sum;
int main()
{
    cin>>num;
    memset(a1,127/3,sizeof(a1));
    memset(a2,127/3,sizeof(a2));
    for(int i=1; i<=num; i++){
        cin>>x;
        t[x]++;
    }
    for(int i=1; i<=20000; i++){
        while(t[i]){
            t[i]--;
            a1[++n1]=i;
        }
    }
    int i=1,j=1;
    k=1;
    while (k<num)
    {
        if(a1[i]<a2[j]){
            w=a1[i];
            i++;
        }
        else{
            w=a2[j];
            j++;
        }
        if(a1[i]<a2[j]){
            w+=a1[i];
            i++;
        }
        else{
            w+=a2[j];
            j++;
        }
        a2[++n2]=w;
        k++;
        sum+=w;
    }
    cout<<sum;
    return 0;
}

一串蠕干倾情提供~qwq

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

今天给大家介绍一种特别好用的排序队列：堆
分为大根堆:priority_queue<类型>队列名
小根堆:priority_queue<类型,vector<类型>,greater<类型> >队列名
根据以上知识便能轻而易举的写出如下的AC代码
#include<iostream>
#include<queue>
#define int long long
using namespace std;
int n,sum;
priority_queue<int,vector<int>,greater<int> >pq;
signed main(){
cin >> n;
while(n--){
int x;cin >> x;
pq.push(x);
}
while(pq.size() > 1){
int x = pq.top();
pq.pop();
int y = pq.top();
pq.pop();
sum += x + y;
pq.push(x + y);
}
cout << sum;
return 0;
}

···cpp
int

优先队列。。。

#include<bits/stdc++.h>
using namespace std;
int n,a,b,ans;
priority_queue<int,vector<int>,greater<int> >q;//重载线性容器，把大数往下推 【两个大于号之间一定要加空格】
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a),q.push(a);
    while(q.size()>1){
        a=q.top();
        q.pop();
        b=q.top();
        q.pop();
        ans+=a+b;//加上体力
        q.push(a+b);//又堆了一堆
    }
    printf("%d",ans);
    return 0;
}

#哈夫曼编码
python3
对于每一堆果子，我们可能要移动多次。
所以抽象出来就是求一个*最优二叉树*
即*节点带权路径长度*和最小的二叉树

n=int(input().strip())
s = list(map(int, input().split()))
cnt = 0

while len(s)>1:
    s.sort()  
        #对数据从小到大排序
    s[1] = s[0]+s[1]  
        #合并最小的两个，作为一个新的节点
    s.pop(0)
    cnt += s[0]
        #计算带权路径

print(cnt)

优先队列无敌!

#include <iostream>
#include <queue>
using namespace std;
int main(int argc, char** argv) {
    priority_queue<int,vector<int>, greater<int>> que;
    int a;
    cin>>a;
    for(int i=0;i<a;i++){
        int b;
        cin>>b;
        que.push(b);
    }
    int e=0;
    while(1){
        int x=que.top();
        que.pop();
        int y=que.top();
        que.pop() ;
        int s=x+y;
        e+=s;
        que.push(s);
        if(que.size()==1){
            break;
        }
    }
    cout<<e<<endl;
    return 0;
}

我c，试了**2遍**，过了
小样，不开long long 见祖宗
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> > str;
int n,Ans,tot,num;
void init(){
int x;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> x;
str.push(x);
}
}
int main(){
init();
while(str.empty() == false)
{
tot += str.top();
str.pop(); num++;
if(num % 2 == 0)
{
Ans += tot;
str.push(tot);
tot = 0;
}
}
cout << Ans;
return 0;
}

此题推荐用优先队列：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    priority_queue<int,vector<int>,greater<int> > q;
    int n,i,x,s,y;
    long long he=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        q.push(x);
    }
    for(i=1;i<=n-1;i++)
    {
        s=q.top();
        q.pop();
        y=q.top();
        q.pop();
        he=he+s+y;
        q.push(s+y);
    }
    cout<<he;
    return 0;
}

//STL大法好
#include<bits/stdc++.h>
using namespace std;
int n,x,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()>=2)
{
int a=q.top(); q.pop();
int b=q.top(); q.pop();
ans+=a+b;
q.push(a+b);
}
cout<<ans<<endl;
return 0;
}

emmm, 试了一下Java TreeMap，ac了，开始还担心内存溢出

import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.concurrent.atomic.AtomicInteger;

public class Main {
    
    public static int getOne(TreeMap<Integer, AtomicInteger> fruitMap) {
        Entry<Integer, AtomicInteger> e = fruitMap.firstEntry();
        int first = e.getKey();
        e.getValue().decrementAndGet();
        if (e.getValue().get() == 0) {
            fruitMap.remove(e.getKey());
        }
        return first;
    }
    
    public static void main(String[] args) {
        
        TreeMap<Integer, AtomicInteger> fruitMap = new TreeMap<>();
        
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i=0;i<n;i++) {
            int fruit = scanner.nextInt();
            fruitMap.putIfAbsent(fruit, new AtomicInteger());
            fruitMap.get(fruit).incrementAndGet();
        }
        scanner.close();
        if (n < 2) {
            System.out.println(0);
            return;
        }
        long total = 0;
        while (true) {
            int combine = getOne(fruitMap) + getOne(fruitMap);
            total += combine;
            if (fruitMap.isEmpty()) {
                break;
            }
            fruitMap.putIfAbsent(combine, new AtomicInteger());
            fruitMap.get(combine).incrementAndGet();
        }
        System.out.println(total);
        
    }
}

蒟蒻一开始循环每次都排序50分

然后蒟蒻在标签的提示下想到了优先队列

C++党有个福利：

我们有** STL ** ！！！

STL里的优先队列 : priority_queue

#include<bits/stdc++.h>
using namespace std;
int n,x,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()>=2){
        int a=q.top(); q.pop();
        int b=q.top(); q.pop();
        ans+=a+b;
        q.push(a+b);
    }
    cout<<ans<<endl;
    return 0;
}

其实用堆也行，但是懒得打了
期待你们理解后AC！

#include <algorithm>
using namespace std;

int main(){
int n;
int arr[10000];
cin >> n;
for(int i = 0; i < n; i++){
cin >> arr[i];
}
int sum = 0;
sort(arr, arr + n);
for(int i = 1 ; i < n; i++){
arr[i] = arr[i] + arr[i-1];
sum = sum + arr[i];
sort(arr + i, arr + n);
}

cout << sum;
}

哈夫曼的套路

#include<iostream>
#include<queue> 
using namespace std;

priority_queue <int, vector<int>, greater<int> > PQ;

int main() {
    int n , tmp, sum = 0;
    cin >> n;
    for (int i = 0 ; i < n ; ++i) {
        cin >> tmp;
        PQ.push(tmp);
    }
        
    while(PQ.size() > 1) {
        tmp = 0;
        for(int i = 0 ; i < 2 ; ++i) {
            tmp += PQ.top();
            PQ.pop();
        }
        
        sum += tmp;
        PQ.push(tmp);
    }
    
    cout << sum << endl;
    return 0;
} 

简单到炸！！

P党

var
  a:array[0..10001] of longint;
  n,i,j,s:longint;
begin
  readln(n);
  for i:=1 to n do
    begin
      read(a[0]);
      j:=i-1;
      while a[0]>a[j] do
        begin
          a[j+1]:=a[j];
          dec(j);
        end;
      a[j+1]:=a[0];
    end;
  for i:=n-1 downto 1 do
    begin
      a[i]:=a[i+1]+a[i];
      s:=s+a[i];
      a[0]:=a[i];
      j:=i-1;
      while a[0]>a[j] do
        begin
          a[j+1]:=a[j];
          dec(j);
        end;
      a[j+1]:=a[0];
    end;
  writeln(s);
end.

解题思路：不断将最小的两个数相加。
使用链式结构来储存数据
需要删减数据，提高效率
通过递归实现多次两个数相加
基例：数据只有1个数的时候-输出结果。
递归链：
1.寻找最小的两个数
2.将一个数变为两数之和
3.将另一个数删去
4.将剩余的数据代入函数

代码比较长，有兴趣的话可以看一下：

#include<iostream>
using namespace std;
typedef struct _node {
    int data;
    struct _node *next;
}Node,*Ptr;
void minpower(Ptr Head, int size) {//计算最小体力
    static int power = 0;
    if (size == 1)cout << power;
    else {
        int Min1=Head->next->data, Min2=Head->next->next->data;
        Ptr p = Head->next->next, M1 = Head->next, M2 = Head->next->next, _M2 = Head->next, _p = p;
        for (int i = 0; i < size-2; i++)//找出最小的两个值
        {
            p = p->next;
            if (Min1 >= Min2 && Min1 > p->data) {
                Min1 = p->data;
                M1 = p;
            }
            else if (Min2 >= Min1 && Min2 > p->data) {
                Min2 = p->data;
                _M2 = _p;
                M2 = p;
            }
            _p = p;
        }
        M1->data = Min1 + Min2;//改变M1的值
        if (_M2->next->next)_M2->next = _M2->next->next;//删除M2
        else _M2->next = NULL;
        delete M2;
        power += Min1 + Min2;
        minpower(Head, size - 1);
    }
}
int main()
{
    int N, num;
    Ptr Head = new Node, p = new Node, Last = p;
    cin >> N;
    Head->next = p;
    for (int i = 0; i < N; i++)//链式储存数据
    {
        Last->next = p;
        cin >> num;
        p->data = num;
        Last = p;
        p = new Node;
        Last->next = NULL;
    }
    delete p;
    minpower(Head, N);
    return 0;
}

用python内置的堆排序模块

import sys
is_py2 = (sys.version_info[0] == 2) #is_py3 = (sys.version_info[0] == 3)
import heapq

N = input()
if is_py2: vals = map(int, raw_input().split()) # python2 用 raw_input()
else: vals = list(map(int, input().split())) # python3加list转换map返回的迭代器

def work_sum(vals):
    # 此行避免输入为[5]之类单元素列表时出错,sum可保证[]被正确处理
    if(len(vals)<=1): return sum(vals)
        
    ans = 0
    heapq.heapify(vals)
    while len(vals) > 1:
        cur_cost = sum([heapq.heappop(vals) for i in range(2)])
        ans += cur_cost
        heapq.heappush(vals, cur_cost)
    return ans

print(work_sum(vals))