【题解】 UVa11292 The Dragon of Loowater

题目大意：

你的王国里有一条n个头的恶龙，你希望雇佣一些骑士把它杀死（即砍掉所有头）。村里有m个骑士可以雇佣，一个能力值为x的骑士可以砍掉恶龙一个直径不超过x的头，且需要支付x个金币。如何雇佣骑士才能砍掉龙的所有头，且需要支付的金币最少？注意，一个骑士只能砍一个头。（且不能被雇佣两次）。输入格式

输入包含多组数据。每组数据的第一行为正整数n和m（1<=n,m<=20000）；以下n行每行为一个整数，即恶龙每个头的直径；以下m行每行为一个整数，即每个骑士的能力。输入结束标志为n=m=0。输出格式

对于每组数据，输出最小花费。如果无解，输出“Loowater is doomed!”。

Solution

显然我们要让勇士砍最适合他的龙，所以就考虑直接排序+贪心就好了...

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<iostream>

#include<queue>

#define ll long long

#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)

using namespace std;

inline int gi(){

	int sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-f;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

inline ll gl(){

	ll sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-f;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

const int N=20010;

int a[N],b[N];

int main(){

	int i,j,n,m,k;

	while(scanf("%d%d",&n,&m)==2 && n && m){

		for(i=1;i<=n;i++)a[i]=gi();

		for(i=1;i<=m;i++)b[i]=gi();

		sort(a+1,a+n+1);sort(b+1,b+m+1);

		int t=1;ll ans=0;

		for(i=1;i<=m && t<=n;i++){

			if(a[t]>b[i])continue;

			ans+=b[i];t++;

		}

		if(t>n)printf("%lld\n",ans);

		else puts("Loowater is doomed!");

	}

	return 0;

}

巴特西

【题解】 UVa11292 The Dragon of Loowater

题目大意：

Solution

最新文章

热门文章