题解：P1097 [NOIP2007 提高组] 统计数字

· · 题解

题解：P1097 [NOIP2007 提高组] 统计数字

思路

这是一道 map 模板练习题。

map 是什么？

map 本质上是一棵红黑树。

怎么定义 map？

map<string, double> sd;

定义一棵红黑树，有两个参数：string 和 double。

怎么使用 map？

sd["abcdefg"] = 3.14159; // 定义 sd 的“第 "abcdefg" 个元素”为 3.14159。
cin >> sd["hijklmn"]; // 输入 sd 的“第 "hijklmn" 个元素”
cout << sd["opq"]; // 输出 sd 的“第 "opq" 个元素”

像一个以 string（即参数一）为下标、值为 double 类型（即参数二）。

如何访问所有已经被使用的元素？

用迭代器。但是和 vector 等的迭代器不同，map 的迭代器指向一个 pair，first 为“下标”，second 为值。

// 访问输出 sd 的每个元素：
for (map<string, double>::iterator it = sd.begin(); it != st.end(); ++it)
{
    cout << it->first << ' ' << it->second << endl;
}
// 或（C++11 起）：
for (auto p : sd)
{
    cout << p.first << ' ' << p.second << endl;
}

如何运用到本题中

用一个 map 储存桶，每次遇到一个元素就让“第【这个数】的值”加一。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
map<int, int> mp;
int main()
{
    cin >> n;
    while (n--)
    {
        int x;
        cin >> x;
        mp[x]++; // 让“第【这个数】的值”加一。
    }
    for (map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
    { // 遍历输出。
        cout << it->first << ' ' << it->second << endl;
    }
    return 0;
}