【題目鏈接】

ybt 1180：分數線劃定
ybt 1946：【09NOIP普及組】分數線劃定
OpenJudge NOI 1.10 05:分數線劃定
洛谷 P1068 [NOIP2009 普及組] 分數線劃定

【題目考點】

1. 排序

【君義精講】排序算法

【解題思路】

該題要排序的元素個數最大為5000，選用$O(n^2)$的排序算法即可。
基本思路為：先按照“先按成績降序排序，成績相同按報名號升序排序”這樣的排序規則對輸入的數據進行排序，取第$?m?1.5?$個人的分數線，再看分數大于等于分數線的人數有多少，再把這些人的信息輸出。
可選的寫法有：

設結構體而后定義結構體變量的排序規則。

直接寫出排序規則

用穩定的排序算法，先按報名號排序，再按成績排序

【題解代碼】

解法1：設結構體，使用sort函數排序

#include <bits/stdc++.h> using namespace std; #define N 5005 struct Stu {int k, s;//k:報名號 s:成績 }; bool cmp(Stu &a, Stu &b) {if(a.s == b.s)//如果分數相同 return a.k < b.k;//報名號小的在前面 else//如果分數不同 return a.s > b.s;//成績高的在前面 } int main() {Stu stu[N];int n, m, line, ct = 0;//line:分數線 ct:人數 cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> stu[i].k >> stu[i].s;sort(stu+1, stu+1+n, cmp);//根據cmp指定的規則進行排序 line = stu[int(m*1.5)].s;//確定分數線for(int i = 1; i <= n; ++i){if(stu[i].s >= line)ct++;}cout << line << ' ' << ct << endl;for(int i = 1; i <= ct; ++i)//輸出前ct個人的信息 cout << stu[i].k << ' ' << stu[i].s << endl;return 0; }

解法2：不用結構體 冒泡排序 直接寫出排序規則

#include <bits/stdc++.h> using namespace std; #define N 5005 int main() { int k[N], s[N], n, m, line, ct = 0;//line:分數線 ct:人數 cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> k[i] >> s[i];for(int i = 1; i <= n - 1; ++i)for(int j = 1; j <= n - i; ++j){if(s[j] < s[j+1] || s[j] == s[j+1] && k[j] > k[j+1])//如果右面的分數高，或分數相同時右面的編號小，要交換{swap(s[j], s[j+1]);swap(k[j], k[j+1]);} }line = s[int(m*1.5)];//確定分數線for(int i = 1; i <= n; ++i){if(s[i] >= line)ct++;}cout << line << ' ' << ct << endl;for(int i = 1; i <= ct; ++i)//輸出前ct個人的信息 cout << k[i] << ' ' << s[i] << endl;return 0; }

解法3：計數排序+插入排序 使用二維數組記錄要輸出的數字，而后輸出

#include <bits/stdc++.h> using namespace std; int score[105][5005] = {};//score[i]:分數為i的各個人的編號 score[i][0]為score[i]這個一維數組的長度 int main() { int k, s, n, m, line, ct = 0;//line:分數線 ct:人數 cin >> n >> m;for(int i = 1; i <= n; ++i){cin >> k >> s;score[s][++score[s][0]] = k;//把k插入score[s]數組，做插入排序，依編號從小到大排序for(int j = score[s][0]; j > 1; --j){ if(score[s][j] < score[s][j-1])swap(score[s][j], score[s][j-1]);elsebreak;}}int lnum = int(m*1.5);//lnum:第幾個人的分數為分數線 for(int i = 100; i >= 0; --i){ct += score[i][0];//分數為i的人有score[i][0]個人if(ct >= lnum){line = i;break; }}cout << line << ' ' << ct << endl;for(int i = 100; i >= line; --i)//輸出分數到line的人的信息for(int j = 1; j <= score[i][0]; ++j)cout << score[i][j] << ' ' << i << endl;return 0; }

解法4：用stable_sort穩定的排序進行兩趟排序

選用任意一種穩定的排序都可以

#include <bits/stdc++.h> using namespace std; #define N 5005 struct Stu {int k, s;//k:報名號 s:成績 }; bool cmp_k(const Stu &a, const Stu &b)//編號比較規則 {return a.k < b.k; } bool cmp_s(const Stu &a, const Stu &b)//分數比較規則 {return a.s > b.s; } int main() {Stu stu[N];int n, m, line, ct = 0;//line:分數線 ct:人數 cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> stu[i].k >> stu[i].s;stable_sort(stu+1, stu+1+n, cmp_k);//先根據編號比較，再根據分數比較stable_sort(stu+1, stu+1+n, cmp_s);//先根據編號比較，再根據分數比較line = stu[int(m*1.5)].s;//確定分數線for(int i = 1; i <= n; ++i){if(stu[i].s >= line)ct++;}cout << line << ' ' << ct << endl;for(int i = 1; i <= ct; ++i)//輸出前ct個人的信息 cout << stu[i].k << ' ' << stu[i].s << endl;return 0; } 新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1180 | 1946：【09NOIP普及组】分数线划定 | OpenJudge NOI 1.10 05 | 洛谷 P1068 [NOIP2009 普及组] 分数线划定的全部內容，希望文章能夠幫你解決所遇到的問題。

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