P1097 题解

ikunTLE · 2025-01-15 22:00:49 · 题解

题目传送门

思路

本题考察 map 的基本语法。

首先考虑桶，对于每一个数，对应的桶增加 1 即可。可是发现数据范围为 1.5\times10^9，普通的数组无法开到这么大，会导致 MLE。

于是考虑 map。读入照常，对于读入的数 x，执行 m_x\gets m_x+1。最后再用 it 遍历一遍 map，分别输出 map 中存储的对应数字及其数量，分别为 it->first 和 it->second。

map 的一次修改是 \mathcal{O}(\log n) 的，所以时间复杂度为 \mathcal{O}(n\log n)，可以通过此题。

AC CODE

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,x;
map<int,int>mp;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&x),++mp[x];
    for(auto it=mp.begin();it!=mp.end();++it)
        printf("%d %d\n",it->first,it->second);
    return 0;
}