众数 I - 详解及代码实现

题目背景

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

样例 #2

样例输入 #2

5 1
1 2 3 4 5

样例输出 #2

pigstd

样例 #3

样例输入 #3

5 1
1 1 2 2 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""≤5"。
Subtask 2（20 pts）："n""≤10^3"。
Subtask 3（20 pts）："k=0"。
Subtask 4（20 pts）："k=1"。
Subtask 5（20 pts）：无特殊限制。

对于 "100%" 的数据，"1""≤n""≤10^6"，"0""≤k""≤n "，"1""≤a_i""≤n"。用C++做出这道题，不要用unordered_map和auto（附代码）内容：### 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    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 - k)
        {
            possibleCount++;
        }
    }

    if (possibleCount == n || k >= possibleCount)
    {
        cout << "pigstd" << endl;
    }
    else
    {
        cout << possibleCount << endl;
    }

    return 0;
}