ZOJ 3705 Applications 模擬題完整解析：多維度評分與排序

題目背景

模擬某高校推免/評優過程。每個學生有姓名、所在戰隊、性別、解題數、代碼行數等屬性。戰隊有排名獎勵，女性加分，解題根據題目類型（毛毛題/舊題/質數題/其他）給分，代碼行數超過 1200 行按公式加分。最終按總分降序、姓名升序輸出前 m 名。

評分規則詳解

算法流程

1. 讀入測試用例數
2. 每用例讀入：n 學生數、m 輸出名額、毛毛題列表、舊題列表、戰隊排名信息
3. 逐學生讀取屬性，計算綜合得分：
       基礎分 0 → +戰隊分 → +性別分 → +各題目分 → +代碼行數分
4. 自定義比較器排序：分數降序，分數相等按姓名字典序升序（用 fabs 比較 double）
5. 輸出前 m 名學生姓名及保留 3 位小數的分數

關鍵實現細節

• 質數判斷：is_prime(n) 試除法至 sqrt(n)
• 浮點數比較：const double eps = 1e-8，排序時 fabs(a-b) < eps 視為相等
• 字符串匹配：strcmp 匹配戰隊名稱
• 代碼行數處理：讀入 c 個 double，降序排序，取 sy[2]（第 4 大）計算加分

完整 C++ 代碼

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
#include <cstring>
using namespace std;

const double eps = 1e-8;

struct Student {
    char name[50];
    double score;
} ss[1005];

int maomao[1000], old[1000];

struct Team {
    char teamname[50];
    int pos;
} ttt[1000];

int is_prime(int n) {
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return 0;
    return 1;
}

int cmp_score(const Student &a, const Student &b) {
    if (fabs(a.score - b.score) < eps) return strcmp(a.name, b.name) < 0;
    return a.score > b.score;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        memset(maomao, -1, sizeof(maomao));
        memset(old, -1, sizeof(old));
        
        int r; scanf("%d", &r);
        for (int i = 0; i < r; i++) scanf("%d", &maomao[i]);
        int s; scanf("%d", &s);
        for (int i = 0; i < s; i++) scanf("%d", &old[i]);
        int q; scanf("%d", &q); getchar();
        for (int i = 0; i < q; i++) scanf("%s %d", ttt[i].teamname, &ttt[i].pos);
        
        for (int i = 0; i < n; i++) {
            char team[50], sex; int pp, c;
            scanf("%s %s %c %d %d", ss[i].name, team, &sex, &pp, &c);
            ss[i].score = 0;
            
            // 隊伍排名分
            for (int j = 0; j < q; j++)
                if (strcmp(team, ttt[j].teamname) == 0) {
                    if (ttt[j].pos == 1) ss[i].score += 36;
                    else if (ttt[j].pos == 2) ss[i].score += 27;
                    else if (ttt[j].pos == 3) ss[i].score += 18;
                    break;
                }
            
            // 性別分
            if (sex == 'F') ss[i].score += 33;
            
            // 解題分
            for (int j = 0; j < pp; j++) {
                int proid; scanf("%d", &proid);
                int flag1 = 0, flag2 = 0;
                for (int k = 0; k < r; k++)
                    if (proid == maomao[k]) { ss[i].score += 2.5; flag1 = 1; break; }
                if (!flag1) {
                    for (int k = 0; k < s; k++)
                        if (proid == old[k]) { ss[i].score += 1.5; flag2 = 1; break; }
                    if (!flag2) {
                        if (is_prime(proid)) ss[i].score += 1;
                        else ss[i].score += 0.3;
                    }
                }
            }
            
            // 代碼行數分
            double sy[1005];
            for (int j = 0; j < c; j++) scanf("%lf", &sy[j]);
            getchar();
            sort(sy, sy + c, [](double a, double b){ return a > b; });
            double rr = 0;
            if (c >= 3) rr = (sy[2] - 1200) * 1.5 / 100;
            ss[i].score += rr;
        }
        
        sort(ss, ss + n, cmp_score);
        for (int i = 0; i < m; i++)
            printf("%s %.3lf\n", ss[i].name, ss[i].score);
    }
    return 0;
}

複雜度與技巧總結

• 時間：O(T × (n × (pp + c log c) + n log n))，完全在限制內
• 核心技巧：多條件加權評分、浮點數排序穩定性、輸入解析細節處理
• 易錯點：質數判斷邊界、代碼行數取第 4 大（索引 2）、戰隊名稱精確匹配

本題是典型的「模擬+排序」綜合題，考察代碼組織能力與邊界條件處理，適合作為模擬類題目進階練習。