勇者斗恶龙(The Dragon of Loowater,UVa 11292 )
你的王国里有一条n 个头的恶龙，你希望雇一些骑士把它杀死(即砍掉所有头)。村里有m 个骑士可以雇佣，一个能力值为x 的骑士可以砍掉恶龙一个直径不超过x 的头，且需要支付x 个金币。如何雇佣骑士才能砍掉恶龙的所有头，且需要支付的金币最少? 注意，个骑士只能砍一个头(且不能被雇佣两次)。
[输入格式]
输入包含多组数据。每组数据的第一行为正整数n和m (1<=n,m<=20000) ，以下n行，每行为一个整数，即恶龙每个头的直径; 以下m 行每行为一个整数，即每个骑士的能力。输入结束标志为n=m=0.
[输出格式]
对于每组数据，输出最少花费。如果无解，输出“Lowterdod
Sample Input
2 3 5 4 7 8 4 2 1 5 5 10 0 0
Sample Output
11
Loowater is doomed!
[分析]
能力强的骑士开价高是合理的，但如果被你派去砍一个很弱的头，就是浪费人才了。因此，可以把雇佣来的骑士按照能力从小到大排序，所有头按照直径从小到大排序，一个个砍就可以了。当然，不能砍掉“当前需要砍的头”的骑士就不要雇佣了。
从资金最少考虑 显然正确。若不这样做可能反而会砍不掉所有头。从小到大排序后，若B[i]能砍
B[i+1]能砍 显然用B[i]，并且B[i+1]可能以后还有更大的发挥空间.
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=20005;
int A[maxn]; //恶龙头的直径
int B[maxn]; //勇士的能力值
int main()
{
int n,m; // 恶龙头数,勇士个数
while(cin>>n>>m)
{
if(n==0&&m==0)
break;
for(int i=0;i<n;i++)
cin>>A[i];
for(int i=0;i<m;i++)
cin>>B[i];
sort(A,A+n);
sort(B,B+m);
int cur=0; //当前要砍头的编号
int cost=0; //当前总费用
for(int i=0;i<m;i++)
{
if(B[i]>=A[cur]) //注意是 >=
{
cost+=B[i];
if(++cur==n) //cur指向下一个头，如果头已砍完，退出循环
break;
}
}
if(cur<n)
cout<<"Loowater is doomed!\n";
else
cout<<cost<<endl;
}
return 0;
}