求一道站外题,谢谢
  • 板块学术版
  • 楼主wangshirui001
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/3/17 20:32
  • 上次更新2023/10/28 06:22:01
查看原帖
求一道站外题,谢谢
324870
wangshirui001楼主2022/3/17 20:32
题目描述

你的王国里有一条有n个头的恶龙,你希望雇一些骑士把它杀死(即砍掉所有的头)。村里有m个骑士可以雇佣,一个能力值为x的骑士可以砍掉一个直径不超过x的头,且需要支付x个金币。如何雇佣骑士才能砍掉恶龙的所有头,且需要支付的金币最少?

注意,一个骑士只能砍一个龙头,且不能被雇佣两次。

输入格式

输入包含多组测试数据。每组测试数据的第一行为正整数n和m,下一行包含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!
问题提示

1≤n,m≤20,000 ,龙头的直径和骑士的能力值都不会超过10,000。

#include<bits/stdc++.h>
using namespace std;
int n,m,r[20010],l[20010],vis[20010],ans;
int main()
{
	while(cin>>n>>m)
	{
		ans=0;
		if(n==0&&m==0)
		{
			break;
		}
		
		for(int i=1;i<=n;i++)
		{
			cin>>r[i];
		}
		for(int i=1;i<=m;i++)
		{
			cin>>l[i];
		}
		if(n>m)
		{
			cout<<"Loowater is doomed!"<<endl;
			continue;
		}
		sort(r+1,r+n+1);
		sort(l+1,l+m+1);
		for(int i=1;i<=n;i++)
		{
			bool flag=true;
			for(int j=1;j<=m;j++)
			{
				if(l[j]>=r[i]&&vis[j]==0)
				{
					ans+=l[j];
					vis[j]==1;
					flag=false;
					break;
				}
                else
                {
                    flag=true;
                }
			}
			if(flag)
			{
				cout<<"Loowater is doomed!"<<endl;
				goto l1;
			}
		}
		cout<<ans<<endl;
		l1:;
	}
}

帮忙看一下我这个怎么错了呗,谢谢

2022/3/17 20:32
加载中...