门禁系统

GitHub跳转原题关系图Canvas 关系图返回列表

按记录顺序维护每个读者编号的出现次数，并输出当前记录的累计次数。

OJ: shumeng

题目 ID: CSP201412A

难度:入门

标签:计数数组

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 样例流程
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

给定 nn 条读者来访记录（每条记录是一个编号），对每条记录输出该编号在此前一共出现过几次。

思路

先看直接扫描此前记录的暴力：

cpp
/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:56
 */
// brute.cpp：小数据暴力解，统计每条记录之前相同编号的出现次数。
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> records(n);
    for (int i = 0; i < n; i++) {
        cin >> records[i];
    }
    for (int i = 0; i < n; i++) {
        int occurrence = 0;
        for (int j = 0; j <= i; j++) {
            if (records[i] == records[j]) {
                occurrence++;
            }
        }
        if (i > 0) {
            cout << ' ';
        }
        cout << occurrence;
    }
    cout << '\n';
    return 0;
}

按记录从左到右处理，count[x] 表示读者 x 已经出现的次数。读到 x 时先执行 count[x]++，再输出它；这样输出值恰好是当前记录的出现次序。

样例流程

样例记录为 1,2,1,1,31, 2, 1, 1, 3：

处理到 执行 输出
1 count[1]++ → 1 1
2 count[2]++ → 1 1
1 count[1]++ → 2 2
1 count[1]++ → 3 3
3 count[3]++ → 1 1

输出序列为 1 1 2 3 1，正好是样例答案。

代码

cpp
/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 22:56
 */
#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> count(n + 1, 0);
    for (int i = 0; i < n; i++) {
        int reader;
        cin >> reader;
        count[reader]++;
        if (i > 0) {
            cout << ' ';
        }
        cout << count[reader];
    }
    cout << '\n';
    return 0;
}

复杂度

每条记录只做一次数组自增，时间复杂度为 O(n)O(n)，空间复杂度为 O(n)O(n)。

总结

顺序统计题的状态只需要保留“之前发生过什么”。把编号映射到计数数组，当前记录先更新再输出即可。