首页 > 代码库 > 统计数字noip2007
统计数字noip2007
7909:统计数字
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
某次科研调查时得到了n个自然数,每个数均不超过1500000000(1.5*109)。已知不相同的数不超过10000个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输出统计结果。
- 输入
- 包含n+1行:
第一行是整数n,表示自然数的个数;
第2~n+1每行一个自然数。
40%的数据满足:1<=n<=1000;
80%的数据满足:1<=n<=50000;
100%的数据满足:1<=n<=200000,每个数均不超过1500 000 000(1.5*10^9)。 - 输出
- 包含m行(m为n个自然数中不相同数的个数),按照自然数从小到大的顺序输出。每行输出两个整数,分别是自然数和该数出现的次数,其间用一个空格隔开。
- 样例输入
-
8 2 4 2 4 5 100 2 100
- 样例输出
-
2 3 4 2 5 1 100 2
一开始想到桶排,但是数据过大。所以换一种方法。升序排序后,从左到右扫,若现在读到的数和他的下一个数相等计数器+1,否则输出
这个数和他的次数,计数器清1 再扫下一个
【代码】
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<algorithm> 5 using namespace std; 6 long long a[200009]; 7 int main() 8 { 9 int n,sum=1; 10 scanf("%d",&n); 11 for(int i=1;i<=n;i++) 12 scanf("%d",&a[i]); 13 sort(a+1,a+n+1);//排序 14 for(int i=1;i<=n;i++) 15 { 16 if(a[i]==a[i+1]) 17 { 18 sum++;//记录相等的个数 19 } 20 else 21 { 22 cout<<a[i]<<" "<<sum<<endl; 23 sum=1;//清1,记录下一个数出现的次数 24 } 25 } 26 return 0; 27 }
统计数字noip2007
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。