发表文章

[最新] 1257: 捕杀恶龙

strivey 19天前 42

1257: 捕杀恶龙

时间限制: 1 Sec  内存限制: 128 MB
提交: 32  解决: 16
您该题的状态:已完成
[提交][状态][讨论版]

题目描述

 动物园有一条n个头的恶龙,你希望雇佣一些骑士把它杀死(也就是砍掉所有的头)。现在有m个骑士可以雇佣,一个能力值为 x 的骑士可以砍掉恶龙一个直径不超过 x 的头,且需要支付 x 个金币。如何雇佣骑士才能砍掉恶龙所有的头,并且支付最小的金币?(注意:一个骑士只能砍一个头并且仅能被雇佣1次。)

输入

输入多组数据,第一行二个整数n、m,(1<=n,m<=20000);以下n行每行为一个整数,即恶龙每个头的直径,以下m行为一个整数,即每个骑士的能力。输入结束标志为n=m=0.

输出

对于每组数据,输出最少花费。如果无解,输出:“Loowater is doomed!”

提示:因为要保证用的钱最少,所以先把骑士按照能力值从小到大进行排序。然后从最小的开始一个一个进行匹配。

样例输入

2 3
5
4
7
8
4
2 1
5
5
10
0 0

样例输出

11
Loowater is doomed!

提示

 

来源

贪心 

 注意了,1、一个能力值为 x 的骑士可以砍掉恶龙一个直径不超过 x 的头   2、m>n

 #include<stdio.h>
#include<algorithm>
using namespace std;
int main() {
    int a[20001],b[20001],i,j;
    int n,m;
    while(scanf("%d %d",&n,&m)&&n&&m) {
        int sum=0;
        for(i=0; i<n; i++) {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        for(i=0; i<m; i++) {
            scanf("%d",&b[i]);
        }
        sort(b,b+m);
        sort(a,a+n);
        int x=0;
        if(m<n) {
            printf("Loowater is doomed!\n");
        } else {
            for(i=0; i<m; i++) {
                if(b[i]>=a[i]) {
                    sum-=b[i];
                    x+=b[i];
                    if(sum<=0) {
                        printf("%d\n",x);
                        break;
                    }
                }
            }
            if(sum>0) {
                printf("Loowater is doomed!\n");
            }
        }
    }
    return 0;
}

相关推荐
最新评论 (0)
返回
发表文章
strivey
文章数
42
评论数
0
注册排名
1305325