tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 电脑基础知识 >>

2007年NOIP提高组第一题解题报告统计数字


1.统计数字
(count.pas/c/cpp) 【问题描述】 某次科研调查时得到了 n 个自然数,每个数均不超过 1500000000(1.5*109)。已知不相同的 数 不超过 10000 个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输 出统 计结果。 【输入】 输入文件 count.in 包含 n+1 行: 第 1 行是整数 n,表示自然数的个数。 第 2~n+1 行每行一个自然数。 【输出】 输出文件 count.out 包含 m 行(m 为 n 个自然数中不相同数的个数),按照自然数从小到大 的顺序输出。每行输出两个整数,分别是自然数和该数出现的次数,其间用一个空格隔开。 【输入输出样例】 count.in 8 2 4 2 4 5 100 2 100 【限制】 40%的数据满足:1<=n<=1000 80%的数据满足:1<=n<=50000 100%的数据满足:1<=n<=200000,每个数均不超过 1 500 000 000(1.5*109) 【主要算法】 1、一道去重排序,本来用基数排序已经足够。但数据范围过大导致超空间,所以可以用快 排先对数列进行排序,形成压缩的作用。 【参考程序】var n,i,q,p,k:longint; a:array[1..200000] of longint; num,s:array[1..10000] of longint; procedure qsort(left,right:longint); var i,j,x,m:longint; 23 42 51 100 2 count.out

begin i:=left;j:=right; m:=a[(left+right)div 2]; repeat while m>a[i] do inc(i); while m<a[j] do dec(j); if j>=i then begin x:=a[i];a[i]:=a[j];a[j]:=x; inc(i);dec(j); end; until i>j; if j>left then qsort(left,j); if i<right then qsort(i,right); end; begin assign(input,'count.in');reset(input); assign(output,'count.out');rewrite(output); readln(n); for i:=1 to n do readln(a[i]); qsort(1,n); // for i:=1 to n do write(a[i],' '); p:=1;q:=2;num[1]:=a[1];k:=1; for i:=1 to 10000 do s[i]:=1; while q<=n do begin if a[p]<>a[q] then begin p:=q;q:=q+1;k:=k+1;num[k]:=a[p];end; while a[p]=a[q] do begin s[k]:=s[k]+1; q:=q+1; end; // write(s[k],' '); end; for i:=1 to k do writeln(num[i],' ',s[i]); close(input); close(output); end.



推荐相关:

NOIP2015提高组解题报告

NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意...所以从前往后扫一遍 DP 统计一下方案就可以了 70 ...已经 取了 k 个互不重叠的非空子串的方案数,...


NOIP2008提高组解题报告

NOIP2008 提高组解题报告 提高组解题报告 石家庄二中 李博杰 1.笨小猴 【问题描述】 输入一个由小写字母构成的字符串,统计出现最多与最少字母的个数,若两数之差...


Noip 2013 提高组 Day2 解题报告

Noip 2013 Day2 解题报告 --By GreenCloudS 第一题:积木大赛 (模拟)直接贪心...(先对高度进行基数排序, 然后逐行计算区间数, 复杂度也是 O(n)) (Cpp): #...


NOIP2008提高组前三题解题报告

[字体:大中小] NOIP2008 提高组前三题解题报告 1...数字的摆法和计算器相同, a,b,c>=0 3、双进程...


NOIP2009提高组解题报告

NOIP2009提高组解题报告NOIP2009提高组解题报告隐藏>>...b1 确定 X 中每项质因子 的最大幂数和最小幂数...取值范围(若为空则说明无解), 并按照乘法原理统计...


NOIP2005提高组解题报告

NOIP2005提高组解题报告_初一理化生_理化生_初中教育...第一题:谁拿了最多的奖学 第一题:谁拿了最多的...以上完成了数据库的建库工作,后面是统计,当然,我们...


NOIP2015提高组day1第二题解题报告

NOIP2015提高组day1第题解题报告_学科竞赛_高中...2. 大概需要什么样的算法根据数据规模,我们可以大概...因为除了最后的查找以外,已经没有什么重复计算的地方...


NOIP2007普及组解题报告

NOIP 2007 普及组解题报告 1、 奖学金 (scholar....任务:先根据输入的 3 门课的成绩计算总分,然后按...100%的数据满足:6<=n<=300 【试题分析】 试题...


NOIP2007提高组复赛试题解题报告

NOIP2007提高组复赛试题解题报告_经济/市场_经管营销_专业资料 暂无评价|0人阅读|0次下载|举报文档 NOIP2007提高组复赛试题解题报告_经济/市场_经管营销_专业资料。...


2011noip提高组复赛题解

个客栈以第 j 种颜色的方案,先以客栈划分第一阶段,以颜色划分第二 阶段,...(); return 0; } Noip 2011 提高组 (Day 2) 解题报告及程序 一、计算...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com