TYVJ P1036 统计数字 Label：坑！！！（用queue+map做出来的水）-白红宇

TYVJ P1036 统计数字 Label：坑！！！（用queue+map做出来的水）

阅读量：7059 次

发布时间：2019-06-28

本文共 1278 字，大约阅读时间需要 4 分钟。

背景

NOIP2007年提高组第一题

描述

某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

输入格式

输入包含n+1行：

第1行是整数n，表示自然数的个数。

第2~n+1行每行一个自然数。

输出格式

输出包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

测试样例1

输入

8

2

4

2

4

5

100

2

100

输出

2 3

4 2

5 1

100 2

备注

40%的数据满足：1<=n<=1000

80%的数据满足：1<=n<=50000

100%的数据满足：1<=n<=200000，每个数均不超过1 500 000 000（1.5*10^9）

代码

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            using namespace std;struct cmp{ bool operator ()(int &a,int &b){ return a>b;//最小值优先 }};map
             
               m;priority_queue
              
               
                ,cmp> que;int N,a[200005];int main(){// freopen("01.txt","r",stdin); scanf("%d",&N); for(int i=1;i<=N;i++){ int x=0; scanf("%d",&x); if(m[x]==0){ que.push(x); } ++m[x]; } while(!que.empty()){ int x=que.top();que.pop(); printf("%d %d\n",x,m[x]); } return 0;}

优先队列比较奇怪，必须这样定义比较函数：

1 struct cmp{2     bool operator ()(int &a,int &b){3         return a>b;//最小值优先4     }5 };

而不能这样：

1 bool cmp(int a,int b){2   return a

还有优先队列的比较函数方向跟sort之类的是相反的（'<'和'>'不一样）

看了下题解直接sort快排不需要优先队列,咔~

不要问我怎么这么无脑,数据范围太大了,想不出好的方法

420ms很危险啊

转载于:https://www.cnblogs.com/radiumlrb/p/5794041.html

你可能感兴趣的文章