UVA 11292 - The Dragon of Loowater (water)

柔情只为你懂 2021-11-19 15:44 172阅读 0赞

[http://uva.onlinejudge.org/index.php?option=com\_onlinejudge&Itemid=8&category=24&page=show\_problem&problem=2267][http_uva.onlinejudge.org_index.php_option_com_onlinejudge_Itemid_8_category_24_page_show_problem_problem_2267]

**题目大意：**n条恶龙，m个勇士，用勇士来杀恶龙。一个勇士只能杀一个恶龙。而且勇士只能杀直径不超过自己能力值的恶龙。每个勇士需要支付能力值一样的金币。问杀掉所有恶龙需要的最少金币？

**题意分析**：先排序，再进行筛选。

#include<stdio.h>
    #include<algorithm> // sort
    #include<iostream>
    #include<string.h>
    using namespace std;
    const int MAXN=20010;
    int A[MAXN],B[MAXN];
    int main()
    {
        int n,m;
        int i,j;
        while(scanf("%d%d",&n,&m)==2 && n && m)
        {
            for(i=0;i<n;i++)scanf("%d",&A[i]);
            for(i=0;i<m;i++)scanf("%d",&B[i]);
            sort(A,A+n);
            sort(B,B+m);
            i=0;
            j=0;
            int ans=0;
            for(i=0;i<n;i++)
            {
                if(j>=m)break;
                while(j<m && A[i]>B[j])j++;
                if(j>=m)break;
                ans+=B[j];
                j++;
            }
            if(i < n) printf("Loowater is doomed!\n");
            else printf("%d\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/riasky/p/3435995.html

[http_uva.onlinejudge.org_index.php_option_com_onlinejudge_Itemid_8_category_24_page_show_problem_problem_2267]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2267

发表评论取消回复

表情：

评论列表（有 0 条评论，172人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 11292 勇者斗恶龙，排序

勇者斗恶龙（The Dragon of Loowater, UVa 11292）你的王国里有一条n个头的恶龙，你希望雇一些骑士把它杀死（即砍掉所有头）。村里有m个骑士可以雇

比眉伴天荒/ 2024年02月17日 21:14/ 0 赞/ 68 阅读

相关 Slay the Dragon 二分 + 贪心

二分+贪心找到最小花费，主要是边界有点麻烦 // Problem: C. Slay the Dragon // Contest: Codeforces - E

柔情只为你懂/ 2022年09月12日 04:49/ 0 赞/ 132 阅读

相关 uva 10934—— Dropping water balloons

题意：给定K个气球，然后n层楼的高度，求确定气球的硬度（站在多高能摔破）思路：递推。dp（i，j）表示最优，那么即dp（i-1，j-1）+1最优，如果K层没有破，

ゝ一世哀愁。/ 2022年08月18日 02:41/ 0 赞/ 124 阅读

相关 uva 437——The Tower of Babylon

题意：给定n个长方体，然后堆积最高的塔，要求上面的面积小于下面的面积。思路：Dp，先把长方体的所有放的情况都构造出来放到数组里，对于当前节点，如果能够在

r囧r小猫/ 2022年08月14日 05:48/ 0 赞/ 157 阅读

相关 uva 1623——Enter The Dragon

题意：有n个装满水的湖，可以预知将来m天下雨情况，每次下满一个湖，或者不下，不下雨的时候可以让某个湖变干，问是否存在一种方案使得每次下雨之前湖总是干的。思路：贪心

以你之姓@/ 2022年08月09日 16:42/ 0 赞/ 168 阅读

相关 The Water Problem——桶排序思想

Think: 1数值位数可用数组表示，思考可否运用桶排序思想 [sdut题目链接][sdut] The Water Problem Time Limit: 1000

港控/mmm°/ 2022年06月16日 02:45/ 0 赞/ 202 阅读

相关 The Dragon of Loowater

Once upon a time, in the Kingdom of Loowater, a minor nuisance turned into a major probl

Bertha 。/ 2022年06月12日 06:08/ 0 赞/ 113 阅读

相关 uva 11292 勇者斗恶龙

![20180224172948549][]![20180224172953636][] 代码： include <bits/stdc++.h> us

落日映苍穹つ/ 2022年05月31日 12:23/ 0 赞/ 166 阅读

相关 uva 11292 Dragon of Loowater （勇者斗恶龙）

![p11292.gif][] Problem C: The Dragon of Loowater Once upon a time, in the Kingdom o

朱雀/ 2021年12月13日 23:17/ 0 赞/ 366 阅读

相关 UVA 11292 - The Dragon of Loowater (water)

[http://uva.onlinejudge.org/index.php?option=com\_onlinejudge&Itemid=8&category=24&page=

柔情只为你懂/ 2021年11月19日 15:44/ 0 赞/ 173 阅读