[NOIP2007-提高] 统计数字

题目描述

给定 $n$ 个自然数，每个数不超过 $1.5 \times 10^9$ ，其中互不相同的数不超过 $10000$ 个。统计每个数出现的次数，并按数值从小到大的顺序输出。

输入：第 1 行整数 $n$ ；接下来 $n$ 行每行一个自然数。输出： $m$ 行（ $m$ 为不同数个数），每行两个整数 值次数。

样例： $8$ 个数 $2,4,2,4,5,100,2,100$ ，输出 $2\ 3, 4\ 2, 5\ 1, 100\ 2$ 。数据范围 $1 \le n \le 200000$ 。

思路

用 map<ll, ll> 一边读入一边计数，map 内部按键升序，直接遍历输出即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 07:19
# update_at: 2026-10-02 07:19

import sys
from collections import Counter


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 自然数的总个数（含重复）
    # 计数后按值升序输出：Counter 一次扫描，排序代价只与不同数个数（≤1e4）相关
    counter = Counter(data)  # 剩余 n 个数全部喂给计数器
    out = [f"{value} {counter[value]}" for value in sorted(counter)]
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 13:51
 * update_at: 2026-10-06 13:52
 */
#include <iostream>
#include <map>
using namespace std;

typedef long long ll;

map<ll, ll> cnt; // 值 -> 出现次数

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

    ll n, x;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> x;
        cnt[x]++; // 哈希计数
    }

    // 按值升序输出每个不同数及其出现次数
    for (map<ll, ll>::iterator it = cnt.begin(); it != cnt.end(); ++it) {
        cout << it->first << ' ' << it->second << '\n';
    }

    return 0;
}

[NOIP2007-提高] 统计数字

目录

题目描述

思路

参考代码