捕杀恶龙
题目描述
动物园有一条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!
- 题解:
这是简单的 贪心问题
分别对骑士的能力和龙头的大小进行从小到大的排序,从龙头最小的开始依次与骑士能力从小到大进行比较,龙头<=骑士能力的,佣金加上。比较下一个龙头
代码:
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{int n,m;while(~scanf("%d %d",&n,&m)&&(n||m)){int a[n],b[m];int sum=0,p=0;for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<m;i++)cin>>b[i];sort(a,a+n);sort(b,b+m);for(int i=0;i<m;i++){for(int j=p;j<n;j++){if(a[j]<=b[i]){sum+=b[i];p++;}break;}}if(sum==0||p<n)cout<<"Loowater is doomed!"<<endl;elsecout<<sum<<endl;}return 0;
}
更多推荐
捕杀恶龙
发布评论