解题报告 P1097 统计数字(NOIP2007TGT1)

题目内容

P1097

解题思路

嗯。。。提高第一题水题。

主要思想还是离散化,可以用HASH做,但我懒得写(不会),于是我选择了万能的map,这个东西真好用。

使用了一个新函数unique(),这个函数拿来在有序的序列中去重,将重复的元素都放回了序列尾端并返回去重后最后一个元素的指针。

代码实现:

#include <map>
#include <cstdio>
#include <algorithm>//sort和unique都定义在algorithm头文件中
#define R register
using namespace std;

const int maxn=200000+5;
map<int,int> m;//map用来存储这个数字出现的次数

int n,a[maxn];

inline int read()//快读
{
    int s=0,w=1;
    R char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}

int main()
{
    int n=read();
    for(R int i=1;i<=n;i++)
    {
        a[i]=read();//读入数据
        m[a[i]]++;//记录次数
    }
    sort(a+1,a+n+1);//先将无序的序列有序化
    int nn=unique(a+1,a+n+1)-(a+1);//去重,再获得去重后剩余元素的个数
    for(R int i=1;i<=nn;i++) printf("%d %d\n",a[i],m[a[i]]);//输出
    return 0;
}

map太好用了