勇者斗恶龙

作者: 新城旧少年 | 来源:发表于2018-07-12 15:53 被阅读3次

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

【输入格式】
第一行为正整数n和m,一下为n+m行,n行为每个头的直径,m行为每个骑士的能力。
【输出格式】
若有最少花费,则输出。若无解,则输出“Loowater is doomed!”。

想法:因为每个勇士只能砍一个头,当然能选能力值小的就选小的,不可能买把砍刀来拍苍蝇,所以先看能力值最小的勇士能不能砍掉最小的头,可以的话就看第二小能力值的勇士能不能砍掉第二小的头,不能的话就舍弃最小能力值的勇士,看第二小能力值的勇士能不能砍掉最小的那个头,然后依次类推。最后,所有头都砍掉的话,那输出使用了的勇士花费总和,如果最强的勇士都出动了,头还没砍完,那就“Loowater is doomed!”

我写的如下

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int A[n],B[m];
    for(int i=0;i<n;i++)
    {
        cin>>A[i];
        
    }
    for(int i=0;i<m;i++)
        cin>>B[i];
    sort(A,A+n);
    sort(B,B+m);
    int q=0,p=0,count=0;
    while(q<n&&p<m)
    {
        if(A[q]<=B[p])
        {
            count+=B[p];
            q++,p++;
            
        }
        else if(A[q]>B[p])
            p++;
    }
    if(q==n)
        cout<<count;
    else 
        cout<<"Loowater is doomed!";
return 0;
}

相关文章

  • 《勇者斗恶龙:决斗者》手游新作即将开启

    近日,SQUARE ENIX 发表了一款名为《勇者斗恶龙:决斗者》(Dragon Quest Rivals)的新作...

  • 勇者斗恶龙

    你的王国里有一条n个头的恶龙,你希望雇佣一些骑士把它杀死(也就是砍掉所有的头)。村里有m个骑士可以雇佣,一个能力值...

  • 勇者斗恶龙

    国王最小的公主是个调皮捣蛋,还很任性的女孩 有一天,公主偷偷溜出皇宫,来到普通人生活的地方游玩,然后遇到了一个少年...

  • 勇者斗恶龙

    《一》在那个恶名昭著的恶龙谷,“公主陛下,今天的夜色看起来,可是相当的不错呢”,恶龙若无其事地对忘了是从何处掳来的...

  • 勇者斗恶龙

    恶龙欲在一处城镇作恶。 一勇者路过,打败了恶龙。 没人夸奖他。 有人说他恃强凌弱。 有人说他想博取名声。 有人说他...

  • 勇者斗恶龙

    从前有个村 村后面有个山 山的对面有个城堡 传说城堡里面住的国王在保护大家 因为在大陆对面是有几只巨大的恶龙的 有...

  • 盘点最终幻想系列中那些有趣的梗

    前面盘点了几个自己常玩又经典的游戏系列《塞尔达传说》、《勇者斗恶龙》、《逆转裁判》、《轩辕剑》、《伊苏》,结果发现...

  • 致敬游戏史上伟大的开创者们!科普各类型游戏最早的起源

    大家都知道《最终幻想》和《勇者斗恶龙》是日式RPG最璀璨的双星,知道《使命召唤》是全球最火爆的FPS,也知道《极限...

  • 勇者斗恶龙--C++

    你的国王中有一条n个头的龙,你希望雇佣一些骑士把它杀死。村里有m个骑士,且只能雇佣一次。 一个能力值为x的骑士,只...

  • 1.勇者斗恶龙

网友评论

本文标题:勇者斗恶龙

本文链接:https://www.haomeiwen.com/subject/wghrpftx.html