UVa 11292 The Dragon of Loowater 【贪心】

时间:2023-03-09 06:16:51
UVa  11292 The Dragon of Loowater 【贪心】

题意:有一条有n个头的恶龙,有m个骑士去砍掉它们的头,每个骑士可以砍直径不超过x的头,问怎样雇佣骑士,使花的钱最少

把头的直径从小到大排序,骑士的能力值也从小到大排序,再一个一个地去砍头

 #include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
using namespace std; typedef long long LL;
const int INF = (<<)-;
const int mod=;
const int maxn=; int a[maxn],b[maxn];
int n,m; int main(){
while(scanf("%d %d",&n,&m) != EOF && n && m){
memset(a,,sizeof(a));
memset(b,,sizeof(b));
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=m;i++) scanf("%d",&b[i]);
sort(a+,a+n+);
sort(b+,b+m+); int ans = ;
int cnt = ;
for(int i=;i<=m;i++){
if(b[i] >= a[cnt]) ans += b[i],cnt++;
if(cnt == n+ ) break;
}
if(cnt <= n) printf("Loowater is doomed!\n");
else printf("%d\n",ans);
}
return ;
}