priority_queue：每次拿走最大的那个

// STL 专题 · priority_queue —— 大根堆和小根堆，只差一个 greater<int>()
//
// ★ 默认是**大根**：top() 永远是最大的那个。依次弹出来就是**从大到小**。
//
//   要「最小的先出」，把三个模板参数写全：
//
//       priority_queue<int, vector<int>, greater<int>> q;
//                          ~~~~~~~~~  ~~~~~~~~~~~~~~~~
//                          元素类型    比较器（← 第 0 块讲的那个，方向反过来）
//
// ⚠ 取值永远是两句：先 top()（看一眼），再 pop()（扔掉）。pop() 自己不给任何值。

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<int> a(n);
  for (int &t : a) cin >> t;

  // ① 默认的大根堆
  priority_queue<int> big;
  for (int t : a) big.push(t);
  cout << "大根堆 top() = " << big.top() << "\n依次弹出：";
  while (!big.empty()) {
    cout << ' ' << big.top();   // ★ 先看
    big.pop();                  // ★ 再扔
  }
  cout << "\n\n";

  // ② 小根堆：三个参数写全
  priority_queue<int, vector<int>, greater<int>> small;
  for (int t : a) small.push(t);
  cout << "小根堆 top() = " << small.top() << "\n依次弹出：";
  while (!small.empty()) {
    cout << ' ' << small.top();
    small.pop();
  }
  cout << '\n';

  return 0;
}

// STL 专题 · priority_queue —— 合并果子：每次取最小的两堆
//
// ★ 「每次取最小的」就是小根堆的字面意思，整个算法只有三句：
//
//       a = q.top(); q.pop();     // 取第一小
//       b = q.top(); q.pop();     // 取第二小
//       q.push(a + b);            // 合出来的那堆再放回去
//
// ⚠ 取**两个**就是两套「top + pop」—— 只取一个，答案就全错了。
// ⚠ 这一题的代价会越加越大，用 long long。

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  priority_queue<long long, vector<long long>, greater<long long>> q;
  for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;
    q.push(x);
  }

  long long total = 0;
  int step = 1;
  // ★ 一直做到只剩一堆（顶上那个）
  while (q.size() > 1) {
    long long a = q.top(); q.pop();
    long long b = q.top(); q.pop();
    long long c = a + b;
    total += c;
    cout << "第 " << step++ << " 步：" << a << " + " << b << " = " << c << "   总代价 " << total << "\n";
    q.push(c);
  }

  cout << "最后剩 " << q.top() << " 这一堆，总代价 " << total << "\n";
  return 0;
}