直接用白書上的翻譯吧
例題1 勇者鬥惡龍（The Dragon of Loowater, UVa 11292）
你的王國裡有一條n個頭的惡龍，你希望雇一些騎士把它殺死（即砍掉所有頭）。村裡有m個騎士可以雇傭，一個能力值為x的騎士可以砍掉惡龍一個直徑不超過x的頭，且需要支付x個金币。如何雇傭騎士才能砍掉惡龍的所有頭，且需要支付的金币最少？注意，一個騎士隻能砍一個頭（且不能被雇傭兩次）。
【輸入格式】
輸入包含多組資料。每組資料的第一行為正整數n和m（1≤n,m≤20 000）；以下n行每行為一個整數，即惡龍每個頭的直徑；以下m行每行為一個整數，即每個騎士的能力。輸入結束标志為n=m=0。
【輸出格式】
對于每組資料，輸出最少花費。如果無解，輸出“Loowater isdoomed!”。
【樣例輸入】
2 3
5
4
7
8
4
2 1
5
5
10
0 0
【樣例輸出】
11
Loowater is doomed!
【分析】
能力強的騎士開價高是合理的，但如果被你派去砍一個很弱的頭，就是浪費人才了。是以，可以把雇傭來的騎士按照能力從小到大排序，所有頭按照直徑從小到大排序，一個一個砍就可以了。當然，不能砍掉“目前需要砍的頭”的騎士就不要雇傭了
證明;
從資金最少考慮 顯然正确。若不這樣做可能反而會砍不掉所有頭。a[i]能砍 a[i+1]能砍 顯然用a[i]，并且a[i+1]可能以後還有更大的發揮空間.
從能将所有頭砍掉的角度來看 若a[i]剛好砍掉 那麼[1..i]的被舍棄騎士顯然也不能砍掉 是以這個角度也是正确的
代碼：
#include<stdio.h>
#include<stdlib.h>
int engry[20100];
int len[20100];
int cmp(const void *i,const void *j)
{
return *(int *)i-*(int *)j;
}
int main()
{
int m,n,i,j=0,ans;
while(scanf("%d%d",&n,&m)!=EOF&&(n!=0||m!=0))
{
ans=0;j=1;
for(i=1;i<=n;i++)
scanf("%d",&len[i]);
for(i=1;i<=m;i++)
scanf("%d",&engry[i]);
if(n>m) { printf("Loowater is doomed!\n");continue;}
qsort(len+1,n,sizeof(len[1]),cmp);
qsort(engry+1,m,sizeof(engry[1]),cmp);
for(i=1;i<=n;i++)
{
while(j!=m+1)
{
if(engry[j]>=len[i])
{
ans+=engry[j];
j++;break;
}
j++;
}
if(j==m+1&&i!=n) break;
}
if(i!=n+1) printf("Loowater is doomed!\n");
else printf("%d\n",ans);
}
return 0;
}
轉載于:https://www.cnblogs.com/zy691357966/p/5480470.html