AtCoder-pakencamp_2021_day2_d 题解

发表于2023-03-27更新于2023-04-03

题目传送门

由于数据问题，我们可以使用 C++STL 里的 map 存储企鹅君选择的答案以及次数……

先定义一个 map，用来储存答题情况。接着将企鹅君的答案存入 map，顺便求出最大值。

1
maxans = max(maxans, mp[x]);

在计算最小值的的答案之前，需要进行特判，因为题目中 MM 的数据达到了可怕的 10910^9，这也是为什么我们要选择使用 map 的原因。

当 M>NM > N 时，说明在 MM 个答案中，其中有一个选项企鹅君必定没有选到，而最小值只能为 00。

1
if (m > n) minans = 0;

否则求剩下的最小值答案即可。

1
2
3
else {
    for (int i = 1; i <= m; i++) minans = min(minans, mp[i]);
}

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
map<int, int> mp;
int n, m, minans = INF, maxans = -INF;
signed main() {
    ios :: sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        mp[x]++;
        maxans = max(maxans, mp[x]);
    }
    if (m > n) minans = 0;
    else {
        for (int i = 1; i <= m; i++) 
            minans = min(minans, mp[i]);
    }
    cout << minans << ' ' << maxans;
    return 0;
}