UVA11292-Dragon of Loowater解法

敘述

有個王國遭受龍群的侵襲，需要聘請騎士把龍全部消滅掉，否則王國會滅亡。

騎士身高(int)必須大於等於龍的頭數(int)才能殺掉龍，每聘用一位騎士需要花費其身高的金幣數(e.g 身高為3的騎士，需要花費3金幣)，每位騎士只能殺死一條龍。

輸入說明

每行輸入兩個整數n,m，分別代表龍群的數量以及騎士的數量，接下來n行資料分別為龍的頭數，接續下去的m行資料為騎士的身高

輸出說明

輸出最小花費金幣數

Solution

題目條件看似很難，需要盡可能殺掉完所有的龍，又要花費最小，但其實只要將資料排序後，一一對應處理，就能找出最小花費了。

假設有4條龍和5位騎士，對應數值如下

龍 : 5 4 3 2
騎士 : 1 7 3 5 6

將資料由小到大做排列之後

龍 : 2 3 4 5
騎士 : 1 3 5 6 7

第一位騎士 1 vs 第一條龍 2 (無法獲勝，即聘用下一位騎士)
第二位騎士 3 vs 第一條龍 2 (獲勝，總花費為3)
第三位騎士 5 vs 第二條龍 3 (獲勝，總花費為3+5)
第四位騎士 6 vs 第三條龍 4 (獲勝，總花費為3+5+6)
第五位騎士 7 vs 第四條龍 5 (獲勝，總花費為3+5+6+7)

求得最小花費為21

程式執行到騎士用完或是龍被殺光時即結束
當龍被殺光時輸出最小花費
當騎士用完時輸出Loowater is doomed!

Code

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
int main() {
    int n, m;
    int i, j;
    int sumN = 0;
    while (scanf("%d %d", &n, &m)) {
        if (n == 0 && m == 0) break;
        int *numN = (int*)malloc(sizeof(int) * n);
        int *numM = (int*)malloc(sizeof(int) * m);
        for (i = 0; i < n; i++) {
            scanf("%d", &numN[i]);
            sumN += numN[i];
        }
        for (j = 0; j < m; j++) {
            scanf("%d", &numM[j]);
        }
        std::sort(numN, numN + n);
        std::sort(numM, numM + m);
        int sum = 0;
        for (i = 0,j = 0; i < n && j < m;) {
            if (numM[j] >= numN[i]) {
                sum += numM[j];
                i++;
                j++;
            }
            else {
                j++;
            }
        }
        if (sum >= sumN)
            printf("%d\n", sum);
        else
            printf("Loowater is doomed!\n");
        sumN = 0;
    }
    return 0;
}