[精品]排序复习

1、?排序法习题1、明明的随机数 (ra ndom.pas/c/cpp) ( PJ2006 )【问题描述】明明想在学校中请一些同学一起做问卷调查，为了实验的客观性，他先用计算机生成了N个1至U 1000之间的随机整数，(NvIOO),对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重“与“排序”的工作。【输入文件】输入文件random.in有2行，第1行为1个正整数，表不所生成的随机数的个数：N第二行有 N个用空格隔开的正整数，为所产生的随机数。【输岀文件】输岀文件random, an

2、s也是2行，第1行为1个正整数M,表示不相同的随机数的个数。第2行 为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。【输入样例】【输岀样例】1020 40 32 67 40 20 89 300 400 15【算法分析】本题十分简单，可以先判重，再排序。至于排序用什么算法, 对，不用担心超时。【程序清单】Program ran dom(l nput. Output);Typelnt=ln teger;Bool=Boolea n;Varh:Arrayl . 1000ofBool;i,j,k, n : I nt ；Begi nAssig n(l nput,'ra ndom.i n

3、*);Reset(I nput);Assig n( Output,'ra ndom.a ns');Rewrite(Output);k:=0;Readl n(n);Fillchar(h,sizeof(h),0);For i:=l to n doBeg inReado );815 20 32 40 67 89 300 400随便吧，这一题数据量太小，怎么做都If n ot hj The nBeg inhj : =True;In c(k);En d;En d;Writel n(k);j: =o ；For i:= 1 to 1000 doIfhi The nBeg inIn c(j);

4、1If j=k The n Writel n(i) Else Write(i, ')En d;Close(I nput);Close(Output);End.2、奖学金（scholar.pas / c / cpp ）（ PJ2007）【问题描述】某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。任务：先根据输入的 3门课的成绩计算总分，然后按

5、上述规则排序，最后按排名顺序输岀前5名学生 的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输岀数据（每行输岀两个数：学号、总分）是：7 2795 279这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是279 （总分等于输入的语文、数学、英语三科成绩之和），但学号为7的学生语文成绩更高一些。如果你的前两名的输岀数据是：5 2797 279则按输出错误处理，不能得分。【输入】输入文件 scholar.in包含行 n+1行：第1行为一个正整数 n,表示该校参加评选的学生人数。第2到年n

6、+1行，每行有3个用空格隔开的数字，每个数字都在 0到100之间。第j行的3个数 字依 次表不学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1? n （恰好是输入数据的行号减l） o所给的数据都是正确的，不必检验。【输出】输岀文件scholar, ans共有5行，每行是两个用空格隔开的正整数，依次表示前5名学生的学号 和总分。【输入输岀样例1】scholar.i n scholar, ans67 89 64678 89 98 690 67 804655487 66 913 25878 89 912 24488 99 771 237【输入输岀样例2scholar.i

7、 n scholar.a ns78 89 91888 99 7780 89 8967 89 6488 98 7878 89 98 890 67 802626487 66 916 2641 2585 258【限制】50%的数据满足：各学生的总成绩各不相同100% 的数据满足： 6v=nv=300【试题分析】简单的排序。因为 nv=300, 所以选择排序不会超时。 存储方面只需存储三个数：学好、语文成绩和总分。【参考程序】program scholar(input,output);varn,x,y,z,i,j integer;a:array1.300,1.3 of integer;procedur

8、e swap(var a,b:integer);vars: integer;begins:=a;a:=b;b:=s;end;beginassign(input, ,scholar.in ,);assign(output,*scholar.ans ,);reset(input);rewrite(output);readln(n);for i:=l to n dobegin readln(x,y,z); ai,l ： =i； ai,2:=x; ai,3:=x+y+z;end;for i:=l to n-1 dofor j:=i+l to n doif (ai,3<aj,3) or (ai,3

9、=aj,3) and (ai,2<aj,2) or (ai,l>aj,l) and (ai,3=aj,3) and (ai,2=aj,2) thenbeginswap(ai,l,aj,l);swap(ai,2,aj,2);swap(ai,3,aj,3) ；end;for i:=l to 5 dowritel n(ai,l,' ai,3)；close(i nput);close(output);end.3、纪念品分组 (group.pas / c / cpp) (PJ2007)纪 且每 乐希望【题目描述】元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的

10、同学所获得的 念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并 组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐 分组的数目最少。你的任务是写一个程序，找岀所有分组方案中分组数最少的一种，输岀最少的分组数目。【输入】输入文件 group.in包含n+2行：第1行包括一个整数 w,为每组纪念品价格之和的上限。第2行为一个整数n,表示购来的纪念品的总件数。第3? n+2行每行包含一个正整数pi(5<=pi<=w),表不所对应纪念品的价格。【输出】输岀文件group.ans仅一行，包含一个整数，即最少的分组数目。【

11、输入输出样例】group.i group.a nsnoo590900200 20300【限制】50%的数据满足：l<=n<=15100% 的数据满足：l<=n<=30000, 80<=w<=200【试题分析】贪心法，先排序，然后按以下贪心策略：设s为所需的组数。i,j为两个指针，开始时指向头和尾。1. 如果 ai+aj<=w, s=:s+l, i:=i+l, j:=j-l 。2. 如果 ai+aj>w, s:=s+l, j:=j-l 。因为*=300000,所以用选择排序可能会超时，最好用快速排序。【参考程序】program group(i np

12、ut,output);w,n ,i,j,s:i nteger;varprocedure qsort(h,t:i nteger);a:aiTayl.,30000 of i nteger;va rp,i,j: integer; begin i:=h; j：=t； P： =ai ； repeat while (aj>p) and (j>i) do if j>i then begin ai ： =aj; i:=i+l;while (ai<p) and (i<j) do i:=i+l; if i<j then begin aj ：=ai; j ： =j-l ；end;

13、end; until i=j; ai ：=P； i:=i+l; j:=j-l; if i<t then qsort(i,t); if j>h then qsort(h,j);end; begin as sign(input, 'group. in'); assign(output,'group, ans'); reset(input); rewrite(output);【深入思考】 快速排序的程序比较难编，是否能有 200,每读入一个数字种比较好编得排序方法呢？答案是肯定的。设x, 就将 px 加 1,这样数字全部读入后就是有序的了，效率甚至比快速排

14、readln(w); readln(n); for i:=l to n do readln(ai);qsort(l,n);i:=l; j：=n; s:=0; while iv j do begin if i=j then begin s:=s+l; break; end;if ai+aj<=w then begin i:=i+l;s:=s+l; end;if ai+aj>w then begin s:=s+l;end;end; writeln(s); close(input); close(output);end.P 数组的下标为 5 至 序还高。这样的话贪心部分也要有所改变。4、

15、分数线划定 (score.pas/c/cpp) (PJ2009)【问题描述】世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才， A 市对所有报 名的选 手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数 的 150% 划 定，即如果计划录取m名志愿者，则面试分数线为排名第m*150% (向下取整)名的选手 的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。现在就请你编写程序划定面试分数线，并输岀所有进入面试的选手的报名号和笔试成绩。【输入】输入文件名为 score.i no第一行，两个整数n, m (5 <n <

16、5000, 3 <m< n),中间用一个空格隔开，其中n表示报名参 加笔试的选手总数，m表示计划录取的志愿者人数。输入数据保证m*150%向下取整后小于等于n。第二行到第n+1行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号k(1000<k<9999)和该选手的笔试成绩s (l<s<100) o数据保证选手的报名号各不相同。【输出】输岀文件 score.anso第一行，有两个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。从第二行开始，每行包含两个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试

17、成绩，按照笔试成绩从高到低输岀，如果成绩相同，则按报名号由小到大的顺序输岀。【输入输出样例】score.i n score.a ns6388 51000 9010053239 8895902390 9595007231 8490011005 9588391001 8888【样例说明】m*150% = 3*150% = 4.5,向下取整后为 4。保证4个人进入面试的分数线为88但因为88有 重分，所以所有成绩大于等于88的选手都可以进入面试，故最终有5个人进入面试。【问题转述】：给岀录取人数及所有面试者成绩，考号。求岀分数线和实际录取人数，并按成绩降序，若成绩相同则考号升序的规则输出录取人考号与

18、成绩。【分析】：双关键字排序。山于n在5000左右，为了确保不 TLE所以需要使用快排等 nlogn的排序。 之后将指针指向计划录取的最后一名，并滑动至与其相同分数的最后一人。则指针之前为实际录取的面试者。【参考程序】Progrram score (in put,output);type an-aiTay1.2 of longint;var i,j, n, m:l ongint;a:aiTay1.,5001 of arr;procedure swap(var a,b:arr);var c:arr;beginc:=a;a:=b;b:=c;end;procedure qsort(l,r:l ongin t);var i,j ,temp 1 ,temp2: longint;begini:=l;j :=r;temp 1 :=random(r-l+1)+1;temp2:=