page_url:https://atcoder.jp/contests/apg4b/tasks/APG4b_bz
問題文
N元素数组 给出了A_1, A_2, \ldots, A_N。 在这个数组的值中,找到出现次数最多的值以及出现的次数。
然而,假设不存在出现次数最多的多重值。
由于限制较大,因此创建程序时请注意计算量。
制約
- 0 \leq N \leq 10^5
- 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 不存在出现次数最多的多重值。
入力
输入是从标准输入按以下格式给出的:
N A_1 A_2 \ldots A_N
出力
値 出現回数
请输出最常出现的值以及出现的次数,以空格分隔。
Judge 还测试除以下输入示例之外的案例。注意。
特别是,判断测试用例包含大量输入,因此请小心不要导致 TLE。
入力例1
5 1 4 4 2 3
出力例1
4 2
输入数组中包含的每个值的出现次数如下。
- 1 出现一次
- 2 出现一次
- 3 出现一次
- 4 出现两次
最大出现次数为 2,其值为 4,因此将输出“4 2”。
入力例2
6 3 2 3 1 3 2
出力例2
3 3
入力例3
1 1000000000
出力例3
1000000000 1
提示
点击打开提示
- “值→出现次数”之间的关系
使用
map进行管理。 向 map添加和访问值的计算复杂度为O(\log N)。- 在这个问题中 有了计算量N^2是10^{10}所以,O(N^2),就变成了TLE。
- N \log N约为。 所需的计算量为1.6*10^6所以,O(N \log N)。
测试输入/输出
只有当你写的程序没有变成AC并且你找不到原因时,请看这个。
单击查看测试输入/输出
测试输入 1
因数据太大而省略
测试输入 2
因数据太大而省略
解答例
观看前请务必亲自尝试一下问题。
点击查看示例答案
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++) {
cin >> A.at(i);
}
map<int, int> cnt;
for (int x : A) {
if (cnt.count(x)) {
// 既に含まれているならインクリメント
cnt.at(x)++;
} else {
// 含まれていないなら、1を追加
cnt[x] = 1;
}
}
int max_cnt = 0; // 出現回数の最大値を保持
int ans = -1; // 出現回数が最大になる値を保持
for (int x : A) {
// 今見ているxの出現回数が、その時点の最大よりも大きければ更新
if (max_cnt < cnt.at(x)) {
max_cnt = cnt.at(x);
ans = x;
}
}
cout << ans << " " << max_cnt << endl;
}