洛谷P1093 [NOIP 2007 普及組] 獎學金 詳解題解
題目背景與要求
題目鏈接：P1093 獎學金
核心任務：根據學生三科總分評選前5名獎學金獲得者，需按特定規則排序輸出。
排序規則（按優先級從高到低）：
- 總分降序：總分高者排名靠前
- 語文降序：總分相同時，語文成績高者優先
- 原始序號升序：前兩項均相同時，按輸入順序排列
算法設計解析
核心思想：多級條件排序
本題本質是多關鍵字排序問題的典型實現，需特別注意以下關鍵點：
| 關鍵維度 | 處理要求 | 實現難點 |
|---|---|---|
| 主排序 | 總分降序 | 正確處理降序比較邏輯 |
| 次排序 | 語文降序 | 避免與總分排序邏輯沖突 |
| 終極條件 | 原始輸入順序 | 需保持輸入順序的穩定性 |
數據結構選擇
采用結構體封裝學生信息，實現數據與邏輯的解耦：
struct Student {int id; // 原始序號（從1開始）int chinese; // 語文成績int math; // 數學成績int english; // 英語成績int total; // 三科總分（可動態計算）
};
自定義比較函數
通過三級條件判斷實現精準排序：
bool compare(const Student& a, const Student& b) {if (a.total != b.total) {return a.total > b.total; // 總分降序}if (a.chinese != b.chinese) {return a.chinese > b.chinese; // 語文降序}return a.id < b.id; // 原始序號升序
}
代碼實現與優化
完整代碼
#include <algorithm>
#include <iostream>
using namespace std;struct Student {int id;int chinese;int math;int english;int total;
};Student students[305];bool compare(const Student& a, const Student& b) {if (a.total != b.total) return a.total > b.total;if (a.chinese != b.chinese) return a.chinese > b.chinese;return a.id < b.id;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;for (int i = 1; i <= n; ++i) {cin >> students[i].chinese >> students[i].math >> students[i].english;students[i].id = i;students[i].total = students[i].chinese + students[i].math + students[i].english;}stable_sort(students + 1, students + n + 1, compare);const int output_count = min(5, n);for (int i = 1; i <= output_count; ++i) {cout << students[i].id << " " << students[i].total << "\n";}return 0;
}
關鍵實現細節
-
穩定排序策略
使用stable_sort而非普通sort，確保當總分和語文成績均相同時，保持原始輸入順序。這是實現第三排序條件的核心保障。 -
輸入輸出優化
通過以下操作將IO效率提升3-5倍：ios::sync_with_stdio(false); cin.tie(nullptr); -
動態總分計算
在輸入時實時計算總分，避免后續重復計算：students[i].total = chinese + math + english;
算法復雜度分析
| 指標 | 復雜度 | 說明 |
|---|---|---|
| 時間復雜度 | O(n log n) | 主導因素為穩定排序操作 |
| 空間復雜度 | O(n) | 存儲學生信息的結構體數組 |
| 額外空間 | O(1) | 原地排序算法 |
測試樣例詳解
輸入示例：
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
輸出解析：
6 265 // 原始序號6，總分98+89+78=265
4 264 // 原始序號4，總分99+88+77=264
3 258 // 原始序號3，總分91+89+78=258
2 244 // 原始序號2，總分91+66+87=244
1 237 // 原始序號1，總分80+67+90=237
關鍵觀察：
- 學生6和學生4總分僅差1分，但語文成績相同（78 vs 88？此處需驗證輸入數據）
- 當總分和語文成績均相同時（如假設存在多個學生），原始序號將決定最終排名
常見錯誤規避
-
排序穩定性缺失
? 錯誤使用sort代替stable_sort
? 必須使用穩定排序保持原始順序 -
比較邏輯錯誤
? 語文成績誤用升序比較
? 需明確降序使用>運算符 -
序號處理不當
? 從0開始編號導致輸出錯誤
? 輸入時保持1-based編號 -
輸出范圍錯誤
? 固定輸出5行導致n<5時越界
? 使用min(5, n)動態控制輸出量
總結與擴展
本題通過結構化數據封裝和自定義比較函數，完整演示了多條件排序的實現范式。其核心思想可擴展至：
- 電商平臺的商品綜合排序（價格+銷量+評價）
- 學生成績多維度排名（總分+單科+考勤）
- 數據庫的多字段排序查詢
掌握穩定排序算法的應用場景，對于處理需要保持相等元素原始順序的排序問題具有重要實踐意義。在實際工程中，可根據具體需求選擇stable_sort或普通sort，并合理設計比較函數的多級條件判斷邏輯。
