(完整word版)排序例題

1、1、明明的隨機(jī)數(shù)( Noip2006) 【問(wèn)題描述】明明想在學(xué)校中請(qǐng)一些同學(xué)一起做一項(xiàng)問(wèn)卷調(diào)查， 為了實(shí)驗(yàn)的客觀性， 他先用計(jì) 算機(jī)生成了 N 個(gè) 1 到 1000 之間的隨機(jī)整數(shù)(NK100),對(duì)于其中重復(fù)的數(shù)字， 只保留一個(gè)， 把其余相同的數(shù)去掉， 不同的數(shù)對(duì)應(yīng)著不同的學(xué)生的學(xué)號(hào)。 然后再 把這些數(shù)從小到大排序，按照排好的順序去找同學(xué)做調(diào)查。請(qǐng)你協(xié)助明明完成 “去重”與“排序”的工作?！据斎胛募枯斎胛募?random.in 有 2 行，第 1 行為 1 個(gè)正整數(shù)，表示所生成的隨機(jī)數(shù)的個(gè)數(shù)： N 第 2 行有 N 個(gè)用空格隔開(kāi)的正整數(shù)，為所產(chǎn)生的隨機(jī)數(shù)?！据敵鑫募枯敵鑫募?random.

2、out 也是 2 行，第 1 行為 1 個(gè)正整數(shù) M 表示不相同的隨機(jī)數(shù) 的個(gè)數(shù)。第 2 行為 M 個(gè)用空格隔開(kāi)的正整數(shù)，為從小到大排好序的不相同的隨機(jī) 數(shù)。【輸入樣例】1020 40 32 67 40 20 89 300 400 15【輸出樣例】815 20 32 40 67 89 300 400【參考程序】/By LYLtimvar n,s:byte;i,min,max,x:word;b:array1.1000of boolean;beginassign(input,random.in);reset(input);assign(output,random.out);rewrite(outp

3、ut);readln(n);fillchar(b,sizeof(b),false);min:=1000;max:=0;s:=0;for i:=1 to n dobeginread(x);bx:=true;if xmax then max:=x;end;close(input);for i:=min to max do if bi then inc(s);writeln(s);for i:=min to max do if bi then write(i, );close(output);end.2、車廂重組( carry.pas )【問(wèn)題描述】在一個(gè)舊式的火車站旁邊有一座橋， 其橋面可以繞河中

4、心的橋墩水平旋轉(zhuǎn)。 一個(gè) 車站的職工發(fā)現(xiàn)橋的長(zhǎng)度最多能容納兩節(jié)車廂， 如果將橋旋轉(zhuǎn) 180 度，則可以把 相鄰兩節(jié)車廂的位置交換， 用這種方法可以重新排列車廂的順序。 于是他就負(fù)責(zé) 用這座橋?qū)⑦M(jìn)站的車廂按車廂號(hào)從小到大排列。 他退休后， 火車站決定將這一工 作自動(dòng)化， 其中一項(xiàng)重要的工作是編一個(gè)程序， 輸入初始的車廂順序， 計(jì)算最少 用多少步就能將車廂排序。【輸入文件】輸入文件有兩行數(shù)據(jù)，第一行是車廂總數(shù)N (不大于 10000),第二行是 N 個(gè)不同的數(shù)表示初始的車廂順序。【輸出文件】一個(gè)數(shù)據(jù)，是最少的旋轉(zhuǎn)次數(shù)?！据斎霕永?carry .in44 3 2 1【輸出樣例】 carry .ou

5、t6【參考程序】/By LYLtimvar n,i,j,t:word;a:array1.10000of word;change:boolean;s:longword;beginassign(input,carry.in);reset(input); assign(output,carry.out);rewrite(output);readln(n);for i:=1 to n do read(ai);close(input);s:=0;i:=1;repeatchange:=false;for j:=1 to n-i doif ajaj+1 then begin t:=aj;aj:=aj+1;a

6、j+1:=t;change:=true; inc(s);end;until not change;end.3、眾數(shù) (masses.pas)【問(wèn)題描述】由文件給出 N個(gè) 1到 30000間無(wú)序數(shù)正整數(shù)， 其中 個(gè)正整數(shù)可能會(huì)出現(xiàn)多次， 出現(xiàn)次數(shù)最多的整數(shù)稱為眾數(shù)。 現(xiàn)的次數(shù)?！据斎敫袷健枯斎胛募谝恍惺钦麛?shù)的個(gè)數(shù) N,第二行開(kāi)始為【輸出格式】輸出文件有若干行，每行兩個(gè)數(shù)，第 1 個(gè)是眾數(shù)，次數(shù)。【輸入樣例】 masses.in122 4 2 3 2 5 3 7 2 3 4 3 【輸出樣例】 masses.out2434【參考程序】/By LYLtimvar n,i,x,min,max,max

7、x:word;a:array1.30000of word;beginassign(input,masses.in);reset(input);assign(output,masses.out);rewrite(output); fillchar(a,sizeof(a),0);min:=30000;max:=0;maxx:=0;readln(n);for i:=1 to n dobegin read(x); if xmax then max:=x; inc(ax);if axmaxx then maxx:=ax; end;for i:=min to max do if ai=maxx then

8、writeln(i, ,ai);close(input);close(output);end.4、第 k 小整數(shù) (knunber.pas) 【問(wèn)題描述】現(xiàn)有 n 個(gè)正整數(shù)，nW10000,要求出這 n 個(gè)正整數(shù)中的第 k 個(gè)最小整數(shù) (相同大小的整數(shù)只計(jì)算一次)，k 1000，正整數(shù)均小于 30000?！据斎敫袷健康谝恍袨?n 和 k，第二行開(kāi)始為 n 個(gè)正整數(shù)的值，整數(shù)間用空格隔開(kāi)?！据敵龈袷健康?k 個(gè)最小整數(shù)的值；若無(wú)解，則輸出“ NO RESUL”T 。【輸入樣例】 knunber.in10 3writeln(s);close(output);K NK10000,同一求出它的眾數(shù)及它

9、出N 個(gè)正整數(shù)。第 2 個(gè)是眾數(shù)出現(xiàn)的1 3 3 7 2 5 1 2 4 6【輸出樣例】 knunber.out3【參考程序】/By LYLtimvar n,k,i,x,min,max,s:word;b:array1.30000of boolean;beginassign(input,knumber.in);reset(input);assign(output,knumber.out);rewrite(output); fillchar(b,sizeof(b),false);min:=30000;max:=0;s:=0; readln(n,k);for i:=1 to n dobeginrea

10、d(x); bx:=true; if xmax thenmax:=x;end; close(input); for i:=min to max do begin if bi then inc(s); if s=kthen begin writeln(i); close(output); halt; end;end;writeln(NO RESULT); close(output);end.5、軍事機(jī)密 (Secret.pas)【問(wèn)題描述】軍方截獲的信息由 n(n=30000)個(gè)數(shù)字組成，因?yàn)槭菙硣?guó)的高端秘密，所以一 時(shí)不能破獲。 最原始的想法就是對(duì)這 n 個(gè)數(shù)進(jìn)行小到大排序， 每個(gè)數(shù)都對(duì)應(yīng)一個(gè)

11、 序號(hào)，然后對(duì)第 i 個(gè)是什么數(shù)感興趣，現(xiàn)在要求編程完成?！据斎敫袷健康谝恍?n,接著是 n 個(gè)截獲的數(shù)字，接著一行是數(shù)字 k,接著是 k 行要輸 出數(shù)的序號(hào)?！据敵龈袷健縦 行序號(hào)對(duì)應(yīng)的數(shù)字?！据斎霕永?Secret.in5121 1 126 123 73243【輸出樣例】 Secret.out7123121【參考程序】/By LYLtimvar n,i,k:word;a:array1.30000of longword;procedure qsort(l,r:longword);var pl,pr,m,t:longword;beginpl:=l;pr:=r;m:=a(l+r)shr 1;r

12、epeatwhile aplm do dec(pr);if plpr;if pll then qsort(l,pr);end;qsortbeginmainassign(input,secret.in);reset(input);assign(output,secret.out);rewrite(output);readln(n);for i:=1 to n do read(ai);qsort(1,n);readl n(k);for i:=1 to k do begin readln(n); writeln(an); end;close(i nput);close(output);end.6、獎(jiǎng)

13、學(xué)金(Noip2007)【問(wèn)題描述】某小學(xué)最近得到了一筆贊助，打算拿出其中一部分為學(xué)習(xí)成績(jī)優(yōu)秀的前 5 名學(xué)生 發(fā)獎(jiǎng)學(xué)金。期末，每個(gè)學(xué)生都有 3 門課的成績(jī)：語(yǔ)文、數(shù)學(xué)、英語(yǔ)。先按總分從 高到低排序，如果兩個(gè)同學(xué)總分相同，再按語(yǔ)文成績(jī)從高到低排序，如果兩個(gè)同 學(xué)總分和語(yǔ)文成績(jī)都相同，那么規(guī)定學(xué)號(hào)小的同學(xué)排在前面，這樣，每個(gè)學(xué)生的排序是唯一確定的。任務(wù)：先根據(jù)輸入的 3 門課的成績(jī)計(jì)算總分，然后按上述規(guī)則排序，最后按排名 順序輸出前 5 名學(xué)生的學(xué)號(hào)和總分。注意，在前 5 名同學(xué)中，每個(gè)人的獎(jiǎng)學(xué)金都 不相同，因此，你必須嚴(yán)格按上述規(guī)則排序。例如，在某個(gè)正確答案中，如果前 兩行的輸出數(shù)據(jù)(每行輸出

14、兩個(gè)數(shù)：學(xué)號(hào)、總分)是：7 2795 279這兩行數(shù)據(jù)的含義是：總分最高的兩個(gè)同學(xué)的學(xué)號(hào)依次是7 號(hào)、5 號(hào)。這兩名同學(xué)的總分都是 279 (總分等于輸入的語(yǔ)文、數(shù)學(xué)、英語(yǔ)三科成績(jī)之和)，但學(xué)號(hào) 為 7 的學(xué)生語(yǔ)文成績(jī)更高一些。如果你的前兩名的輸出數(shù)據(jù)是：5 2797 279則按輸出錯(cuò)誤處理，不能得分。【輸入格式】輸入文件 scholar.in 包含 n+1 行：第 1 行為一個(gè)正整數(shù) n，表示該校參加評(píng)選的學(xué)生人數(shù)。第 2 到 n+1 行,每行有 3 個(gè)用空格隔開(kāi)的數(shù)字，每個(gè)數(shù)字都在 0 到 100 之間。第 j 行的3 個(gè)數(shù)字依次表示學(xué)號(hào)為 j-1 的學(xué)生的語(yǔ)文、數(shù)學(xué)、英語(yǔ)的成績(jī)。每個(gè)學(xué)

15、生的學(xué)號(hào)按照輸入順序編號(hào)為 1n (恰好是輸入數(shù)據(jù)的行號(hào)減 1)。所給的數(shù)據(jù) 都是正確的，不必檢驗(yàn)?！据敵龈袷健枯敵鑫募?scholar.out 共有 5 行，每行是兩個(gè)用空格隔開(kāi)的正整數(shù)，依次表示前 5 名學(xué)生的學(xué)號(hào)和總分?！据斎胼敵鰳永?1】scholar.i nscholar.out66 26590 67 804 26487 66 913 25878 89 912 24488 99 771 23767 89 6478 89 98【輸入輸出樣例 2】scholar.i nscholar.out88 26580 89 892 26488 98 786 26490 67 801 25887 6

16、6 915 25878 89 9188 99 7767 89 6478 89 98【限制】50%的數(shù)據(jù)滿足：各學(xué)生的總成績(jī)各不相同100%勺數(shù)據(jù)滿足：6=*=300【參考程序】/By LYLtimtypeno de=record i,ch:byte; sum:word; end; arr=array1.300of no de;var n: word;stu:arr;ma,e n:byte;procedure in it;var i:word;beg inassig n(i nput,scholar.i n);reset(i nput);readl n(n);for i:=1 to n dobe

17、gi nstui .i:=i; read(stui.ch);readl n( ma,e n);stui.sum:=stui.ch+ma+e n;end;close(i nput);en d;i nitprocedure merge(l,m,r:word);var pt,pl,pr:word;tmp:arr;beg inpt:=l;pl:=l;pr:=m+1;while(pl=m)a nd(prstupr.sum)or(stupl.sum=stupr.sum)and(stupl.ch=stupr.ch)thenbegin tmppt:=stupl; inc(pt); inc(pl); end e

18、lse begintmppt:=stupr; inc(pt); inc(pr); end;while pl=m do begin tmppt:=stupl; inc(pt); inc(pl); end;while pr=r then exit;m:=(l+r)1;mergesort(l,m);mergesort(m+1,r); merge(l,m,r);end;mergesortprocedure print;var i:byte;begin assign(output,scholar.out);rewrite(output); for i:=1 to 5 do writeln(stui.i,

19、stui.sum); close(output);end;printbeginmaininit;mergesort(1,n);print;end.7、統(tǒng)計(jì)數(shù)字 (Noip2007)【問(wèn)題描述】某次科研調(diào)查時(shí)得到了 n 個(gè)自然數(shù)，每個(gè)數(shù)均不超過(guò) 1500000000(1.5*109 ) 已知不相同的數(shù)不超過(guò) 10000 個(gè)，現(xiàn)在需要統(tǒng)計(jì)這些自然數(shù)各自出現(xiàn)的次數(shù)， 按照自然數(shù)從小到大的順序輸出統(tǒng)計(jì)結(jié)果?！据斎敫袷健枯斎胛募?count.in 包含 n+1 行：第 1 行是整數(shù) n ，表示自然數(shù)的個(gè)數(shù)。第 2n+1 行每行一個(gè)自然數(shù)?！据敵龈袷健枯敵鑫募?count.out 包含 m 行(m 為 n

20、 個(gè)自然數(shù)中不相同數(shù)的個(gè)數(shù))，按照自然數(shù)從小到大的順序輸出。 每行輸出兩個(gè)整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn) 的次數(shù)，其間用一個(gè)空格隔開(kāi)?！据斎胼敵鰳永縞oun t.i ncoun t.out82 324 245 12100 2451002100【限制】40%的數(shù)據(jù)滿足：1=*=100080%的數(shù)據(jù)滿足：1=n=50000100%的數(shù)據(jù)滿足：11;repeatwhile aplm do dec(pr);if pl=pr;if pll then qsort(l,pr);end;qsortprocedure work;var i,k:longword;beginassign(output,count.

21、out);rewrite(output);an+1:=maxlongint;k:=1;for i:=2 to n+1 doif aiai-1 then begin writeln(ai-1, ,k); k:=1;endelse inc(k);close(output);end;workbeginmaininit;qsort(1,n);work;end.分?jǐn)?shù)(mark)：【問(wèn)題描述】 問(wèn)題描述：高考分?jǐn)?shù)剛剛公布，共有N個(gè)人參加考試，為了有便于填寫志 愿，教育部把所有考生的成績(jī)平均分成m檔。保證n是m的倍數(shù)。 考試成績(jī)?cè)?k-1)*(n/m)+1名到k*(n/m)名的考生被分配到K檔 (k=1,2,3m)。并列第i名的所有考生都被分配到K擋(k=1,2,3m),并列i