STL 容器（本书只用到这几个）　例题与练习

// 例题 ①「合并果子（小规模版）」—— STL 容器组
//
// 每次都要「取出当前最小的那个」⇒ 小根堆。这正是第 37 章那道原题。
// ⚠ 这一长串 priority_queue<int, vector<int>, greater<int>> 背下来就行：
//    三个参数分别是「装什么」「底下用什么容器装」「怎么比」，
//    中间那个 vector<int> 是默认值，只是因为要写第三个，才不得不把它补上。

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

int main() {
    int n;
    cin >> n;

    priority_queue<int, vector<int>, greater<int>> q;   // 小根堆：top() 是最小的
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        q.push(x);
    }

    long long cost = 0;
    while (q.size() >= 2) {
        int a = q.top(); q.pop();     // ⚠ pop() 不返回值 —— 要先 top() 拿到再 pop()
        int b = q.top(); q.pop();
        cost += a + b;
        q.push(a + b);
    }

    cout << cost << "\n";
    return 0;
}

// 例题 ②「每个单词出现了几次」—— STL 容器组
//
// map 就是「下标可以是任意类型的数组」。
// cnt[w]++ 时如果这个键还不存在，它会**自动新建、值从 0 开始** —— 不用先判断。
// 而 map 的键是**自动有序**的，所以遍历出来天然就是字典序，一句排序都不用写。

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

int main() {
    map<string, int> cnt;
    string w;
    while (cin >> w) cnt[w]++;        // 读到文件结尾为止

    for (const auto &kv : cnt)        // kv.first 是键（单词），kv.second 是值（次数）
        cout << kv.first << ' ' << kv.second << "\n";
    return 0;
}