UVA11292 Dragon of Loowater

落魄码农在线炒粉 lv.1

发布时间：2022-11-28 11:27:25 710

相关标签： # c++

题目链接：https://vjudge.net/problem/UVA-11292
题意：有n只龙，每个龙的能力为x，你有m个勇士，每个勇士的能力为y，你需要雇佣n个勇士去杀这n只龙，每个勇士雇佣费用为y，每个勇士只能被雇佣一次，且只能斩杀能力不超过y的龙，问你要杀掉这些龙的最少花费
解析：先把龙和勇士都排个序，然后从能力小的勇士开始找他能杀的龙，这样的花费就是最小的

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn],b[maxn];
int main(void)
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        if(!n && !m) break;
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<m;i++)
            scanf("%d",&b[i]);
        sort(a,a+n);
        sort(b,b+m);
        int ans = 0,cnt = 0;
        for(int i=0;i<m;i++)
        {
            if(b[i]>=a[cnt])
            {
                cnt++;
                ans += b[i];
            }
            if(cnt==n)
                break;
        }
        if(cnt==n)
            printf("%d\n",ans);
        else
            puts("Loowater is doomed!");
    }
    return 0;
}

文章来源： https://blog.51cto.com/u_11435021/5880210

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。