- 论坛徽章:
- 0
|
比基堡海滩有一个有n个触手的恐怖水母,蟹老板希望雇佣一些海绵宝宝把它杀死(即
砍掉所有触手)。现在有m个海绵宝宝可以雇佣,一个能力值为x的海绵宝宝可以砍掉恐怖水母一只直径不超过x的触手,且需要支付x个金币。如何雇佣海绵宝宝
才能杀死水母,并且支付的金币最少?需要注意一个海绵宝宝只能砍掉一只触手,并且不能被雇佣两次。
Input
第1行为正整数n和m,第2行为水母n只触手的直径,第3行为m个海绵宝宝的能力值,所有数据用空格间隔。
Output
输出最少金币数。如果无解,输出NULL
#include<stdio.h>
void BS(int A[],int n)
{
int i,j,t;
for (i=0;i<n-1;i++)
{
for(j=0;j<n-j-1;j++)
{
if(A[j]<A[j+1])
t=A[j],A[j]=A[j+1],A[j+1]=t;
}
}
}
int main()
{
int SM[100],BB[100],Q[100],n,m,i,j,w;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
scanf("%d",&SM[i]);
for(i=0;i<m;i++)
scanf("%d",&BB[i]);
BS(SM,n);
BS(BB,m);
if(SM[0]>BB[0])
{
printf("NULL\n");
w=0;
}
int k=0;
for (i=0;w!=0&&i<n;i++)
{
for(j=k;j<m;j++)
if(SM[i]<=BB[j])
Q[i]=BB[j],
k=j+i;
break;
}
int sum=0;
for(i=0;i<n;i++)
sum+=Q[i];
printf("%d",sum);
}
return 0;
} |
|