7909:统计数字
2018-06-17 22:59:30来源:未知 阅读 ()
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
- 来源
- NOIP2007复赛 提高组 第一题
- 分析:
- 一开始以为是一个二分兼快拍的难题。。
- 当我一脸懵逼的看着满是超时的结果时。。
- 我才恍然发现
- 这TM就是一个简单的线性数据处理
- !!!!!!!!!!!!!!
- 啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
-
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 int a[10000001]; 6 struct node 7 { 8 int daxiao; 9 int cishu; 10 }b[10000001]; 11 int now=1; 12 int main() 13 { 14 int n; 15 cin>>n; 16 for(int i=1;i<=n;i++) 17 { 18 cin>>a[i]; 19 } 20 sort(a+1,a+1+n); 21 for(int i=1;i<=n;i++) 22 { 23 if(a[i]==a[i+1]) 24 { 25 b[now].cishu++; 26 continue; 27 } 28 else 29 { 30 b[now].daxiao=a[i]; 31 b[now].cishu++; 32 now++; 33 } 34 } 35 for(int i=1;i<=now-1;i++) 36 { 37 cout<<b[i].daxiao<<" "<<b[i].cishu<<endl; 38 } 39 return 0; 40 }
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 using namespace std; 5 struct node 6 { 7 int daxiao; 8 int cishu; 9 }a[1000001]; 10 int now=1; 11 int rf(int l,int r,int x) 12 { 13 int mid=(l+r)/2; 14 if(a[mid].daxiao==x) 15 { 16 a[mid].cishu++; 17 return 1; 18 } 19 else if(l>=r) 20 return 0; 21 else 22 { 23 if(x>a[mid].daxiao) 24 return rf(l,mid,x); 25 else 26 return rf(mid+1,r,x); 27 } 28 } 29 int comp(const node & a,const node & b) 30 { 31 if(a.daxiao>b.daxiao) 32 return 1; 33 else 34 return 0; 35 } 36 int main() 37 { 38 int n; 39 cin>>n; 40 for(int i=1;i<=n;i++) 41 { 42 int b; 43 scanf("%d",&b); 44 if(rf(0,i,b)==1) 45 continue; 46 else 47 { 48 a[now].daxiao=b; 49 a[now].cishu++; 50 now++; 51 } 52 sort(a+1,a+i+1,comp); 53 } 54 55 for(int i=n;i>=1;i--) 56 { 57 if(a[i].cishu!=0) 58 cout<<a[i].daxiao<<" "<<a[i].cishu<<endl; 59 } 60 return 0; 61 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:C++学习 cout的格式化输出
下一篇:1006. 捡石头
- 1164 统计数字 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash