06 · 桶计数：用值当下标

第 4 节的数组，下标是位置：a[0] 是第 0 个读进来的数，a[i] 是第 i 个。这一节换一种用法：让下标等于值本身。cnt[x] 读作“值等于 x 的元素有几个”。数组还是那个 int[]，变的只是下标的含义。

先看这段骨架。本节剩下的内容，都是在解释它为什么成立、什么时候不成立：

int cnt[1001];                        // 值域 0..1000，所以要 1001 个桶

for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    ++cnt[x];                         // 值 x 出现一次，就让第 x 号桶加一
}

for (int x = 0; x <= 1000; ++x)       // 按下标从小到大扫一遍
    for (int k = 0; k < cnt[x]; ++k)
        cout << x << " ";             // 输出自动升序，一次 sort 都没调用

这几行同时干完三件事：统计（每个值出现几次）、去重（同一个桶只算一次）、排序（下标从小到大就是值的从小到大）。代价是开 1001 个格子。

本节没有新的标准库函数。要拆的是数组的新用法：格子怎么开、cnt[x]++ 到底做了什么、什么时候该用 “= 1” 而不是 “++”。

int cnt[1005];               // 全局：值域 1..1000，全自动清零

int main() {
    int n;  cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;  cin >> x;
        ++cnt[x];            // 值 x 出现一次，第 x 号桶加一
    }
    cout << cnt[7] << "\n";  // 值 7 出现了几次
    return 0;
}

int cnt[10] = {0};

cnt[3]++;  cnt[3]++;  cnt[9]++;        // 值 3 出现 2 次，值 9 出现 1 次
cout << cnt[3] << " " << cnt[9];       // 2 1

int x = 3;
if (cnt[x] > 0) --cnt[x];              // “消耗”一个 3：配对、匹配类题目的常用写法

int vis[1005];                    // 0 = 没出现，1 = 出现过

vis[42] = 1;                      // 标记值 42 存在
if (vis[42])  cout << "有 42\n";
if (!vis[7])  cout << "没有 7\n";

cnt[20] = 1;   // 读到 20，给 20 号格子打勾
cnt[40] = 1;
cnt[20] = 1;   // 又读到一个 20：本来就是 1，再写一次还是 1 —— 去重是免费的

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

// cnt[x] = 1 表示“值 x 出现过”，0 表示没出现。
// 值域是 1..1000，下标最多用到 1000；开 1005 是手滑余量。
// 放在 main 外面：全局数组由系统清零，省掉一次手动清零，也不占栈空间。
int cnt[1005];

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

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        cnt[x] = 1;          // 用 = 1 而不是 ++cnt[x]：只要“出现过”，不要次数
    }

    int m = 0;               // 题目要求先输出个数，所以先数一遍
    for (int x = 1; x <= 1000; ++x)
        if (cnt[x]) ++m;

    cout << m << "\n";

    bool first = true;       // 控制空格：第一个数前面不输出空格，行末就不会多出空格
    for (int x = 1; x <= 1000; ++x)
        if (cnt[x]) {
            if (!first) cout << " ";
            first = false;
            cout << x;
        }
    cout << "\n";
    return 0;
}

// 输入 n 个数（值 1..1000，允许重复），升序全部输出
int cnt[1005];

int main() {
    int n;  cin >> n;
    for (int i = 0; i < n; ++i) { int x; cin >> x; ++cnt[x]; }

    for (int x = 1; x <= 1000; ++x)
        for (int k = 1; k <= cnt[x]; ++k)    // 出现几次就打印几次
            cout << x << " ";
    cout << "\n";
}

// 值域是 -50..50 的温度：整体平移 50，下标变成 0..100
int cnt[101];
for (int i = 0; i < n; ++i) {
    int t;  cin >> t;
    ++cnt[t + 50];                 // -50 -> 0, 0 -> 50, 50 -> 100
}
cout << cnt[50] << "\n";           // 温度 0 对应下标 50

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

int a[105];
int have[20005];      // have[v] = 1 表示值 v 在集合里
int used[20005];      // used[v] = 1 表示值 v 已经算过一次答案

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

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        have[a[i]] = 1;                  // 存在性标记：值当下标
    }

    int ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) {      // j 从 i+1 开始，两个加数必定不同
            int s = a[i] + a[j];
            if (s <= 20000 && have[s] && !used[s]) {
                used[s] = 1;             // 同一个和只记一次
                ++ans;
            }
        }

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