P1097 题解

思路

本题考察 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

CPP

#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;
}

文章操作

思路

相关推荐

评论

P1097 题解