uva 11292 The Dragon of Loowater(贪心)
2024-10-21 07:41:51
题目大意:
你的王国里有一条n个头的恶龙,你希望雇一些骑士把它杀死(即砍掉所有头)。村里有m个骑士可以雇佣,一个能力值为x的骑士可以砍掉恶龙一个直径不超过x的头,且需要支付x个金币。如何雇佣骑士才能砍掉恶龙的所有头,且需要支付的金币最少?注意,一个骑士只能砍一个头(且不能被雇佣两次)。
输入格式
输入包含多组数据。每组数据的第一行为正整数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!
/*
能力强的骑士开价高是合理的,但如果被你派去砍一个很弱的头,就是浪费人才了。
因此,可以把雇佣来的骑士按照能力从小到大排序,所有头按照直径从小到大排序
一个一个砍就可以了。
当然,不能砍掉“当前需要砍的头”的骑士就不要雇佣了
从资金最少考虑 显然正确。若不这样做可能反而会砍不掉所有头。
a[i]能砍 a[i+1]能砍 显然用a[i],并且a[i+1]可能以后还有更大的发挥空间.
从能将所有头砍掉的角度来看
若a[i]刚好砍掉 那么[1..i]的被舍弃骑士显然也不能砍掉 所以这个角度也是正确的
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std;
int n,m,x,ans,cur;
int a[],b[]; bool cmp(int a,int b)
{
if(a>b) return ;
else return ;
} int main()
{
while(scanf("%d%d",&n,&m))
{
ans=;cur=;
if(n==&&m==) return ;
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);
for(int i=;i<m;i++)
{
if(b[i]>=a[cur])
{
ans+=b[i];
if(++cur==n)
break;
}
}
if(cur<n) cout<<"Loowater is doomed!"<<endl;
else
cout<<ans<<endl;
}
return ;
}
心若向阳 无谓悲伤
最新文章
- 23.实现一个名为Person的类和它的子类Employee,Employee有两个子类Faculty 和Staff。 具体要求如下: (1)Person类中的属性有:姓名name(String类型),地址address(String类型), 电话号码telphone(String类型)和电子邮件地址email(String类型); (2)Employee类中的属性有:办公室office(Stri
- Javascript动画效果(三)
- 【Composer】实战操作一:使用库
- Linux下*.tar.gz文件解压缩命令
- 【2011 Greater New York Regional 】Problem H: Maximum in the Cycle of 1
- shell笔记(基本知识)
- ISO14443协议中,卡片对RATS,PPS,IBLOCK的处理约定
- ssh登录的时候,根本不给输入密码的机会,直接拒绝,是因为BatchMode的设置
- 【Java IO流】对象的序列化和反序列化
- MongoDB,分组,聚合
- NSString的几种常用方法—韩俊强博…
- day-10初级函数
- c# 图片插入Excel
- Html.Partial,Html.RenderPartial Html.Action,Html.RenderAction区别
- javac编译带包的java文件需要在命令处加参数
- CentOS 修改用户密码
- 004-React-Native--多图选择上传
- Day Four
- 阿里云启用IPV6
- gulp教程之gulp中文API