Dragon of Loowater UVA - 11292 勇者斗恶龙 贪心
程序员文章站
2024-03-19 08:16:10
...
你的王国里有一条n个头的恶龙,你希望雇一些骑士把它杀死(即砍掉所有头)。村里有m个骑士可以雇佣,一个能力值为x的骑士可以砍掉恶龙一个直径不超过x的头,且需要支付x个金币。如何雇佣骑士才能砍掉恶龙的所有头,且需要支付的金币最少?注意,一个骑士只能砍一个头(且不能被雇佣两次)。
分析:两者都排序,在knights中从小到大依次寻找的符合当前最小dragon的knight值。如果遍历完knights都不能凑够n个骑士除龙则失败。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 20000 + 5;
int dragons[N], knights[N];
int main(int argc, char** argv) {
int n, m;
while( scanf("%d%d",&n,&m) == 2 && n && m){
for(int i = 0; i < n; i++)
scanf("%d",&dragons[i]);
for(int i = 0; i < m; i++)
scanf("%d",&knights[i]);
sort(dragons, dragons+n);
sort(knights, knights+m);
int cur = 0, ans = 0;
for(int i = 0; i < m; i++){
if( knights[i] >= dragons[cur]){
ans += knights[i];
if( ++cur == n) break;
}
}
if(cur == n) printf("%d\n",ans);
else printf("Loowater is doomed!\n");
}
return 0;
}
【输入格式】
输入包含多组数据。每组数据的第一行为正整数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!