勇者斗恶龙(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 
    
     #include 
     
      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
      
       >A[i];        for(int i=0;i
       
        >B[i];        sort(A,A+n);        sort(B,B+m);        int cur=0;  //当前要砍头的编号        int cost=0; //当前总费用        for(int i=0;i
        
         =A[cur])  //注意是 >=           {               cost+=B[i];               if(++cur==n)  //cur指向下一个头，如果头已砍完，退出循环                break;           }        }        if(cur