切換
舊版
前往
大廳
主題

ZeroJudge - d774: NOIP2009 2.分數線劃定 解題心得

Not In My Back Yard | 2020-10-12 00:00:06 | 巴幣 2 | 人氣 141

題目連結:


題目大意:
輸入第一列給定兩正整數 n 、 m (5 ≦ n ≦ 5000 , 3 ≦ m ≦ n),代表有 n 個選手參加筆試,並且設定一分數界線為,分數由大排到小後的第 m × 1.5 (取整數)個人的成績。

接著有 n 列輸入,每列給定兩正整數 k 、 s (1000 ≦ k ≦ 9999 , 1 ≦ s ≦ 100),代表一位選手的報考編號以及筆試成績。

請找出所有通過分數界線(也就是分數大於等於界線)的人之編號以及成績。第一列輸出分數界線之值以及通過人數,其後的列數每列即是一位選手的編號和成績。

選手的輸出順序依照成績由大排到小,成績一樣的按照報考編號由小排到大。



範例輸入:
6 3
1000 90
3239 88
2390 95
7231 84
1005 95
1001 88


範例輸出:
88 5
1005 95
2390 95
1000 90
1001 88
3239 88


解題思維:
用一結構(Struct)將選手的編號與成績存在一起,然後將整個結構按照題目的要求排序(先成績大到小,再看編號小到大)。

接著看第 m × 1.5 (取整數)個人的成績為何,該值即是分數界線之值。然後從該人之後開始看後面的人之成績,直到碰到第一個成績小於分數界線的人或是看完了所有選手(此時代表該人其後的選手之成績皆跟他一樣),便可以知道有多少個人通過。

最後就輸出那些通過的人之編號以及成績即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作