uva 10954 - Add All

/*

Problem link

Type: Adhoc - greedy, Data structure - priority queue

*/

 1  #include <iostream>
 2  #include <cstdio>
 3  #include <cstring>
 4  #include <cmath>
 5  #include <vector>
 6  #include <queue>
 7  
 8  using namespace std;
 9  
10  priority_queue<int, vector<int>, greater<int> > list;
11  int n;
12  
13  int main()
14  {
15      while (true)
16      {
17          cin >> n;
18          if (n==0) break;
19          for (int i=1; i<=n; i++)
20          {
21              int value;
22              cin >> value;
23              list.push(value);
24          }
25          int result = 0;
26          while (list.size()>1)
27          {
28              int a = list.top(); list.pop();
29              int b;
30              if (!list.empty())
31              {
32                  b = list.top();
33                  list.pop();
34              } else b = 0;
35              list.push(a+b);
36              result += a+b;
37          }
38          cout << result << endl;
39          while (!list.empty()) list.pop();
40      }
41      return 0;
42  }