众数 I - C++ 解题思路与代码详解
众数 I - C++ 解题思路与代码详解
**题目背景**
pigstd 是一个可爱的男孩子。他在 NOI2022 中的众数一题定义了 \(10^6\) 个 ``std::deque`` 并没有 MLE。
**题目描述**
给定一个长度为 \(n\) 的序列 \(a\)，我们通过以下方式构造序列 \(b\)：
- 初始时 \(b=a\)。
- 依次对 \(b\) 进行 \(k\) 次操作，每次操作选择任意一个元素并将其**修改**为任意整数。
dXqwq 定义一个序列的**众数**为所有出现次数最大的数。例如 \([1,1,4,5,1,4]\) 的众数为 \(1\)，而 \([1,14,5,14,19,19,8,10]\) 的众数为 \(14,19\)。
你需要求出有多少整数可能成为 \(b\) 的**众数**。
**输入格式**
第一行输入两个整数 \(n,k\)。
第二行输入 \(n\) 个整数 \(a_i\)。
**输出格式**
输出一个整数，代表可能成为众数的数的数量。
特别地，如果答案为正无穷，输出 ``pigstd``。
**样例 #1**
样例输入 #1
5 0 1 2 3 4 5
样例输出 #1
5
**样例 #2**
样例输入 #2
5 1 1 2 3 4 5
样例输出 #2
pigstd
**样例 #3**
样例输入 #3
5 1 1 1 2 2 3
样例输出 #3
3
**提示**
**【样例解释】**
对于第一组数据，最终 \(1,2,3,4,5\) 可能为区间众数。
对于第二组数据，将第一个数换成 \(6,7,8,9,\cdots\) 后它们均会成为区间众数，因此答案为正无穷。
对于第三组数据，\(1,2,3\) 可能成为区间众数。
**【提示】**
开 \(10^6\) 个 ``std::deque`` 在空间限制为 1024MB 时不一定会 MLE。
**【数据范围】**
**本题采用捆绑测试。**
- Subtask 1（20 pts）：\(n\leq 5\)。
- Subtask 2（20 pts）：\(n\leq 10^3\)。
- Subtask 3（20 pts）：\(k=0\)。
- Subtask 4（20 pts）：\(k=1\)。
- Subtask 5（20 pts）：无特殊限制。
对于 \(100\%\) 的数据，\(1\leq n\leq 10^6\)，\(0\leq k\leq n \)，\(1\leq a_i\leq n\)。
**解题思路**
首先统计原序列中每个数出现的次数。如果 \(k=0\)，那么可能的众数数量就是出现次数最大的数的数量。如果 \(k\geq 1\)，我们可以通过修改操作将任意一个数的出现次数增加到与当前出现次数最大的数相同，所以可能的众数数量为正无穷。
**C++ 代码实现**
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
unordered_map<int, int> count;
for (int i = 0; i < n; i++) {
cin >> a[i];
count[a[i]]++;
}
int maxCount = 0;
for (auto it = count.begin(); it != count.end(); it++) {
maxCount = max(maxCount, it->second);
}
int possibleCount = 0;
for (auto it = count.begin(); it != count.end(); it++) {
if (it->second == maxCount) {
possibleCount++;
}
}
if (k == 0 || possibleCount == 1) {
cout << possibleCount << endl;
} else {
cout << "pigstd" << endl;
}
return 0;
}
**代码解释**
- 使用 ``unordered_map`` 统计每个数出现的次数。
- 找到出现次数最大的数。
- 统计出现次数与最大次数相同的数的数量。
- 根据 \(k\) 的值判断可能的众数数量。
**总结**
这道题的关键在于理解题目描述中“修改”操作的含义，以及如何利用这个操作来构造可能的众数。代码实现相对简单，主要是利用了 ``unordered_map`` 的统计功能。
原文地址: https://www.cveoy.top/t/topic/pOgM 著作权归作者所有。请勿转载和采集!