https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2267
有一条n个头的恶龙,现在有m个骑士可以雇佣去杀死他,一个能力值为x的勇士可以砍掉直径不超过x的头,而且需要支付x个金币。如何雇佣才能砍掉所有的头且支付最少的金币,注意一个勇士只能砍一个头,也只能被雇佣一次。
输入包含多组数据,每组数据第一行为正整数n,m(1<=n,m<=20000),以下n行每行为一个整数,就是恶龙的头的直径,以下m行每行为一个整数,就是每个骑士的能力值。输入结束标志位m=n=0。
输出格式对于每组数据输出最少花费,如果无解,则输出"Loowater is doomed!"。
输入样例
2 3
5
4
7
8
4
2 1
5
5
10
0 0
这个题意思是挺好理解的,就是x>=n,而且x不能重复使用,本来我是按照习惯
for(int i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(b[j]>=a[i])
{
s=s+b[j];
break;
}
}
}
好吧,后来又想x只能用一次啊,然后就改成j=i,但是结果还是不对,然后想数据,发现还是不行,就看了一下书,他是把j放在前面的,
然后就改成了这个
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,i,m,a[20000],b[20000];
while(cin>>n>>m)
{
if(n==0&&m==0)
break;
int s=0;
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(int j=0;j<m;j++)
{
cin>>b[j];
}
sort(a,a+n);
sort(b,b+m);
for(int j=0;j<m;j++)
{
for(i=j;i<n;i++)
{
if(b[j]>=a[i])
{
s=s+b[j];
break;
}
}
}
if(i<n||s==0)
{
cout<<"Loowater is doomed!"<<endl;
}
else
cout<<s<<endl;
}
return 0;
}
最后判断输出什么是如果骑士的个数少于恶龙的头,那么无论怎么样都不行,如果s==0那也代表没办法
哎,好多天没打代码了,什么都忘了,今天下定决心好好好学。