九度 OJ 1014 排名問題：C++ 解法詳解

題目大意

給定考生數 N、題數 M、及格線 G、各題分值，以及每位考生解出的題號。計算每位考生總分，篩選總分 ≥ G 的考生，按分數降序、准考證號升序輸出。

輸入輸出範例

輸入：
4 5 25
10 10 12 13 15
CS004 3 5 1 3
CS003 5 2 4 1 3 5
CS002 2 1 2
CS001 3 2 3 5
1 2 40
10 30
CS001 1 2
2 3 20
10 10 10
CS000000000000000001 0
CS000000000000000002 2 1 2
0

輸出：
3
CS003 60
CS001 37
CS004 37
0
1
CS000000000000000002 20

核心演算法

1. 讀取題目分值存入陣列 grade[1..M]。
2. 遍歷每位考生，累加其解出題目的分值得到 total。
3. 若 total >= G，存入結構體陣列/向量。
4. 自定義比較函數：分數降序，分數相同則准考證號升序（字串比較）。
5. 排序後輸出符合條件的人數與名單。

C++ 參考代碼

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

struct Person {
    string id;
    int score;
};

bool cmp(const Person& a, const Person& b) {
    if (a.score != b.score) return a.score > b.score;
    return a.id < b.id;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, G;
    while (cin >> N, N != 0) {
        cin >> M >> G;
        vector grade(M + 1);
        for (int i = 1; i <= M; ++i) cin >> grade[i];

        vector vec;
        for (int i = 0; i < N; ++i) {
            Person p;
            int m;
            cin >> p.id >> m;
            p.score = 0;
            for (int j = 0; j < m; ++j) {
                int t; cin >> t;
                p.score += grade[t];
            }
            if (p.score >= G) vec.push_back(p);
        }

        sort(vec.begin(), vec.end(), cmp);
        cout << vec.size() << '\n';
        for (auto& p : vec) cout << p.id << ' ' << p.score << '\n';
    }
    return 0;
}

複雜度分析

• 時間：O(N × M + K log K)，K 為及格人數（K ≤ N）。
• 空間：O(N + M)。

常見陷阱

• 准考證號長度可達 20 字元，需用 string 儲存。
• 多測試案例，讀到 N=0 結束。
• 考生可能解出 0 題（m=0），分數為 0。