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 ;
}