有一条n个头的恶龙，现在有m个骑士可以雇佣去杀死他，一个能力值为x的勇士可以砍掉直径不超过x的头，而且需要支付x个金币。如何雇佣才能砍掉所有的头且支付最少的金币，注意一个勇士只能砍一个头，也只能被雇佣一次。

输入包含多组数据，每组数据第一行为正整数n,m（1<=n,m<=20000)，以下n行每行为一个整数，就是恶龙的头的直径，以下m行每行为一个整数，就是每个骑士的能力值。输入结束标志位m=n=0。

输出格式对于每组数据输出最少花费，如果无解，则输出"Loowater is doomed!"。

SAMPLE INPUT

2 3

2 1

0 0

SAMPLE OUTPUT

Loowater is doomed!

嗯...最小的花费，肯定会想到贪心的思想...当然这道题里有轻微的贪心思想。

思路：

将龙的头按照直径的长短从小到大排序，将勇士的能力值从小到大排序（为了不浪费勇士的能力值），然后进行比较...

鬼畜一——cur：

注意我们要记录龙已经被砍掉几个头，并且下一个要砍哪一个，所以用cur来记录，并且最后cur要和n进行比较，看看是否将龙所有的头都砍完了..

鬼畜二——输入：

输入与平常不同，只有输入到 0 0 时才会停止，所以要用一个while循环嵌套所有

大体过程：

输入 ------> 贪心思想的排序 --------> 比较 --------> 是否能将所有的头砍去 ---------> 根据情况输出

下面是AC代码：

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int maxn = ;

 int j[maxn], d[maxn];

 //j数组表示骑士的能力值

 //d数组表示龙头的直径 

 int main(){

     int n, m;

     while(scanf("%d%d", &n, &m) ==  && n && m){//while循环进行输入，n，m不得为0

         for(int i = ; i <= n; i++) scanf("%d", &d[i]);

         for(int k = ; k <= m; k++) scanf("%d", &j[k]);

         sort(d+, d+n+); //排序

         sort(j+, j+m+);

         int cost = , cur = ;//cost为最小花费，cur为鬼畜一

         for(int i = ; i <= m; i++){

             if(j[i] >= d[cur]){//进行比较

                 cost += j[i];

                 if(++cur == n) break;//将龙头全砍掉

             }

         }

         if(cur < n) printf("Loowater is doomed!\n");//没砍完龙头

         else printf("%d\n", cost);

     }

     return ;

 }

巴特西

UVa 11292 勇者斗恶龙(The Dragon of Loowater)

有一条n个头的恶龙，现在有m个骑士可以雇佣去杀死他，一个能力值为x的勇士可以砍掉直径不超过x的头，而且需要支付x个金币。如何雇佣才能砍掉所有的头且支付最少的金币，注意一个勇士只能砍一个头，也只能被雇佣一次。

SAMPLE INPUT

SAMPLE OUTPUT

嗯...最小的花费，肯定会想到贪心的思想...当然这道题里有轻微的贪心思想。

思路：

将龙的头按照直径的长短从小到大排序，将勇士的能力值从小到大排序（为了不浪费勇士的能力值），然后进行比较...

鬼畜一——cur：

注意我们要记录龙已经被砍掉几个头，并且下一个要砍哪一个，所以用cur来记录，并且最后cur要和n进行比较，看看是否将龙所有的头都砍完了..

鬼畜二——输入：

输入与平常不同，只有输入到 0 0 时才会停止，所以要用一个while循环嵌套所有

大体过程：

输入 ------> 贪心思想的排序 --------> 比较 --------> 是否能将所有的头砍去 ---------> 根据情况输出

下面是AC代码：

最新文章

热门文章