30-懶省事的小明（priority_queue）

　​​​​

　　　　　　　　　　　　　　

描述

      小明很想吃果子，正好果園果子熟了。在果園裡，小明已經将所有的果子打了下來，而且按果子的不同種類分成了不同的堆。小明決定把所有的果子合成一堆。 因為小明比較懶，為了省力氣，小明開始想點子了:

　　每一次合并，小明可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經過n-1次合并之後，就隻剩下一堆了。小明在合并果子時總共消耗的體力等于每次合并所耗體力之和。 

　　因為還要花大力氣把這些果子搬回家，是以小明在合并果子時要盡可能地節省體力。假定每個果子重量都為1，并且已知果子的種類數和每種果子的數目，你的任務是設計出合并的次序方案，使小明耗費的體力最少，并輸出這個最小的體力耗費值。 

　　例如有3種果子，數目依次為1，2，9。可以先将1、2堆合并，新堆數目為3，耗費體力為3。接着，将新堆與原先的第三堆合并，又得到新的堆，數目為12，耗費體力為12。是以小明總共耗費體力=3+12=15。可以證明15為最小的體力耗費值。

輸入

第一行輸入整數N(0<N<=10)表示測試資料組數。接下來每組測試資料輸入包括兩行，第一行是一個整數n(1<＝n<=12000)，表示果子的種類數。第二行包含n個整數，用空格分隔，第i個整數ai(1<＝ai<=20000)是第i種果子的數目。

輸出

每組測試資料輸出包括一行，這一行隻包含一個整數，也就是最小的體力耗費值。

樣例輸入

1
3 
1 2 9      

樣例輸出

15      

​

#include <iostream>
#include <queue>
using namespace std;
struct node{
  int x;
  bool friend operator <(const  node a, const node b){  //必須用友元函數？？？ 
    return a.x > b.x;
  }
}; 

int main(){
  std::ios::sync_with_stdio(false);
  int t;
  cin >> t;

  while(t--){
    int n;
    node x;
    priority_queue <node> qq;
    cin >> n; 
    for(int i = 0; i < n; i++){
      cin >> x.x ;
      qq.push(x);
    }
    long long ans = 0;
    while(qq.size() > 1){
      node a = qq.top();
      qq.pop();
      node b = qq.top();
      qq.pop();
//      cout << a. x << "dddd" << b.x  << endl;
      a.x = a.x + b.x;
      ans += a.x;
      qq.push(a);
    }
    cout << ans << endl;
  }

  return 0;
}