描述 Description 世博會志愿者的選拔工作正在?A?市如火如荼的進行。為了選拔最合適的人才，A?市對 所有報名的選手進行了筆試，筆試分數達到面試分數線的選手方可進入面試。面試分數線根 據計劃錄取人數的150%劃定，即如果計劃錄取m名志愿者，則面試分數線為排名第m*150% （向下取整）名的選手的分數，而最終進入面試的選手為筆試成績不低于面試分數線的所有 選手。 現在就請你編寫程序劃定面試分數線，并輸出所有進入面試的選手的報名號和筆試成 績。

輸入格式 InputFormat 輸入文件名為?score.in。 第一行，兩個整數n，m（5?≤?n?≤?5000，3?≤?m?≤?n），中間用一個空格隔開，其 中n?表示報名參加筆試的選手總數，m?表示計劃錄取的志愿者人數。輸入數據保證m*150% 向下取整后小于等于n。 第二行到第?n+1?行，每行包括兩個整數，中間用一個空格隔開，分別是選手的報名號k （1000?≤?k?≤?9999）和該選手的筆試成績s（1?≤?s?≤?100）。數據保證選手的報名號各 不相同。

輸出格式 OutputFormat 輸出文件?score.out。 第一行，有兩個整數，用一個空格隔開，第一個整數表示面試分數線；第二個整數為 進入面試的選手的實際人數。 從第二行開始，每行包含兩個整數，中間用一個空格隔開，分別表示進入面試的選手 的報名號和筆試成績，按照筆試成績從高到低輸出，如果成績相同，則按報名號由小到大的 順序輸出。

樣例輸入 SampleInput?[復制數據] 6 3 1000 90 3239 88 2390 95 7231 84 1005 95 1001 88

樣例輸出 SampleOutput?[復制數據] 88 5 1005 95 2390 95 1000 90 1001 88 3239 88

時間限制 TimeLimitation 各個測試點1s

來源 Source NOIP2009普及組?第二題

算法：簡單排序

?1?//Noip?2009?Problem?2?score
?2?//Oier:Shylocks
?3?type?n=record
?4?????k,s:integer;
?5?????end;
?6?var?a:array[1..5000]of?n;
?7?????nn,m,i,score:integer;
?8?Procedure?swap(var?a,b:integer);
?9?var?temp:longint;
10?begin
11???temp:=a;
12???a:=b;
13???b:=temp;
14?end;
15?Procedure?qsort(l,r:longint);
16?var?i,j,mid,mid2:integer;
17?begin
18???i:=l;
19???j:=r;
20???mid:=a[(i+j)?div?2].s;
21???mid2:=a[(i+j)?div?2].k;
22???repeat
23?????while(a[i].s<mid)or?(a[i].s=mid)and(a[i].k>mid2)do?inc(I);
24?????while(a[j].s>mid)or?(a[j].s=mid)and(a[j].k<mid2)do?dec(j);
25?????if?i<=j?then
26?????begin
27???????swap(a[i].s,a[j].s);
28???????swap(a[i].k,a[j].k);
29???????inc(i);dec(j);
30?????end;
31???until?i>j;
32???if?i<r?then?qsort(i,r);
33???if?l<j?then?qsort(l,j);
34?end;
35?begin
36???readln(nn,m);
37???score:=trunc(m*1.5);
38???//writeln(score);
39???for?i:=1?to?nn?do?readln(a[i].k,a[i].s);
40???qsort(1,nn);
41???while(a[nn-score+1].s=a[nn-score].s)do?inc(score);
42???writeln(a[nn-score+1].s,'?',score);
43???for?i:=nn?downto?nn-score+1?do?writeln(a[i].k,'?',a[i].s);
44?end.

轉載于:https://www.cnblogs.com/shy-/archive/2012/10/25/2739965.html

總結

以上是生活随笔為你收集整理的[1025]Noip 2009 Problem 2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。