經典算法題「北理工的惡龍」：貪心策略與 qsort 實戰

經典算法題「北理工的惡龍」：貪心策略與 qsort 實戰

問題背景

北理工出現一只多頭噴火惡龍，校長召集勇士斬殺。規則：

• 龍有 n 個頭（直徑各異），勇士 m 人（身高各異）。
• 勇士身高 ≥ 龍頭直徑才能斬下該頭。
• 每斬一頭，校長付出等同勇士身高的學分。
• 目標：用最少總學分斬掉所有龍頭，否則輸出 "bit is doomed!"。

算法分析：貪心 + 排序

要使總學分最小，應優先派遣身高最低但能勝任的勇士去斬當前最小的龍頭。因此：

1. 將龍頭直徑數組 dragon[] 升序排序。
2. 將勇士身高數組 soldier[] 升序排序。
3. 雙指針遍歷：i 指向當前龍頭，j 指向當前勇士。
4. 若 soldier[j] >= dragon[i]，該勇士斬頭成功，累加學分，i++、j++（每人只能斬一頭）。
5. 否則 j++ 尋找下一位更高勇士。
6. 若龍頭未斬完而勇士用盡（j > m），任務失敗。

關鍵代碼實現

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b; // 升序比較函數
}

int main() {
    int n, m;
    int dragon[102] = {0}, soldier[102] = {0};
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &dragon[i]);
    for (int i = 1; i <= m; i++) scanf("%d", &soldier[i]);

    qsort(dragon + 1, n, sizeof(int), cmp);
    qsort(soldier + 1, m, sizeof(int), cmp);

    int sum = 0, i = 1, j = 1;
    for (; i <= n; i++) {
        if (j > m) { printf("bit is doomed!\n"); return 0; }
        if (soldier[j] >= dragon[i]) {
            sum += soldier[j++];
        } else {
            while (j <= m && soldier[j] < dragon[i]) j++;
            if (j > m) { printf("bit is doomed!\n"); return 0; }
            sum += soldier[j++];
        }
    }
    printf("%d\n", sum);
    return 0;
}

qsort 詳解

qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))

• base：待排序數組首地址（如 dragon+1 從下標 1 開始）。
• nmemb：元素個數。
• size：單個元素大小（sizeof(int)）。
• compar：比較函數指針，返回負/零/正表示小於/等於/大於。

避坑指南

• 勇士斬頭成功後，必須同時移動龍頭和勇士指針（i++ 和 j++），否則會重複使用勇士。
• 數組下標從 1 開始需注意 qsort 參數調整。
• 輸入規模較小（≤100），O(n log n) 排序完全足夠。