首页 > 试题广场 > 回合制游戏
[编程题]回合制游戏
  • 热度指数:2737 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
你在玩一个回合制角色扮演的游戏。现在你在准备一个策略,以便在最短的回合内击败敌方角色。在战斗开始时,敌人拥有HP格血量。当血量小于等于0时,敌人死去。一个缺乏经验的玩家可能简单地尝试每个回合都攻击。但是你知道辅助技能的重要性。
在你的每个回合开始时你可以选择以下两个动作之一:聚力或者攻击。
    聚力会提高你下个回合攻击的伤害。
    攻击会对敌人造成一定量的伤害。如果你上个回合使用了聚力,那这次攻击会对敌人造成buffedAttack点伤害。否则,会造成normalAttack点伤害。
给出血量HP和不同攻击的伤害,buffedAttack和normalAttack,返回你能杀死敌人的最小回合数。

输入描述:
第一行是一个数字HP
第二行是一个数字normalAttack
第三行是一个数字buffedAttack
1 <= HP,buffedAttack,normalAttack <= 10^9


输出描述:
输出一个数字表示最小回合数
示例1

输入

13
3
5

输出

5
#include<iostream>
using namespace std;
int main()
{ 
    int HP;
    cin >> HP;
    int nA, bA;
    cin >> nA;
    cin >> bA;
    int count = 0;
    if (HP <= nA) {
        cout << 1;
        return 0;
    }
    else {
        if (2 * nA >= bA) {//当蓄力的伤害不高于普通伤害的二倍的时候,全用普通伤害就行了
            while (HP > 0) {
                HP -= nA;
                count++;
            }
        }
        else {//当蓄力的伤害高于普通伤害的二倍的时候,尽可能多打蓄力伤害,判断最后是不是只需打一次普通伤害就行了
            while (HP > nA) {
                HP -= bA;
                count += 2;
            }
            if (HP > 0) count++;
        }
    }
    cout << count;
    return 0;
}

发表于 2019-07-26 21:40:03 回复(0)

刚刚写的博客,同步到牛客一下~https://blog.csdn.net/weixin_39350124/article/details/91345870

解法1(深度优先搜索)

(case通过率只有75%,想AC的可以直接看解法2)
用一个int变量buffed,当buffed=1表示buffedAttack,buffed=0表示normalAttack,然后每次进入递归方法都有两种决策方式。具体Code如下所示:

import java.util.HashMap;
import java.util.Scanner;

public class Main {

    public static HashMap<String, Integer> map = new HashMap<>(); //用于记忆化搜索

    /**
     * @param hp 当前hp
     * @param normalAttack 普通攻击
     * @param buffedAttack 辅助攻击
     * @param isBuffed 本回合是否使用辅助攻击
     * @param cur 当前回合数
     * @return
     */
    public static int process(int hp, int normalAttack, int buffedAttack, int isBuffed, int cur) {
        String str = isBuffed + "_" + hp; //用isBuffed和hp作为记忆化搜索的key

        //每次进入递归之前先搜索是否有缓存结果
        if (map.containsKey(str)) {
            return map.get(str);
        }
        //如果hp < 1,返回需要的回合
        if (hp < 1) {
            map.put(str, cur); //返回结果前加缓存
            return cur;
        }

        int res = 0;
        if (isBuffed == 1) {
            //如果上回合用buffedAttack,则这回合直接减去敌人生命值
            res = process(hp - buffedAttack, normalAttack, buffedAttack, 0, cur + 1);
        } else {
            //如果上回合使用normalAttack,则这回合有两种决策方式
            res = Math.min(process(hp - normalAttack, normalAttack, buffedAttack, 0, cur + 1),
                    process(hp, normalAttack, buffedAttack, 1, cur + 1));
        }
        map.put(str, res); //返回结果前加缓存
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int hp = sc.nextInt();
        int normal = sc.nextInt();
        int buffed = sc.nextInt();
        //一开始有两种选择
        int a = process(hp, normal, buffed, 1, 1); //蓄力
        int b = process(hp - normal, normal, buffed, 0, 1); //普通攻击
        System.out.println(Math.min(a, b));
    }
}

解法2(数学规律)

直接用数学规律去分析:
1)如果buffedAttack <= 2 * normalAttack,那么一定全程使用normalAttack更划算
2)如果buffedAttack > 2 * normalAttack,那么优先使用buffedAttack更划算,如果hp % normalAttack > 0,当余数小于normalAttack,最后一回合用normalAttack就能杀死敌人;如果hp % normalAttack == 0,那么一定全程使用buffedAttack更划算。
具体Code如下:

import java.util.Scanner;

public class Main {

    public static int func(int hp, int normalAttack, int buffedAttack) {
        int res = 0;
        /**
         * 如果buffedAttack > 2 * normalAttack,那么一定优先使用buffedAttack划算
         */
        if (buffedAttack > 2 * normalAttack) {
            res = hp % buffedAttack;
            /**
             * 如果hp % normalAttack > 0
             * 当余数小于normalAttack,最后一回合用normalAttack就能杀死敌人
             * 其它情况,一直使用buffedAttack攻击
             */
            if (res > 0 && res <= normalAttack) {
                res = (hp / buffedAttack) * 2 + 1;
            } else {
                res = ((hp - 1) / buffedAttack) * 2 + 2;
            }
        } else {
            /**
             * 如果buffedAttack <= 2 * normalAttack,一直单回合普通攻击更划算
             */
            res = (hp - 1) / normalAttack + 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int hp = sc.nextInt();
        int normal = sc.nextInt();
        int buffed = sc.nextInt();
        System.out.println(func(hp, normal, buffed));
    }
}
发表于 2019-06-08 16:55:54 回复(1)
#include <bits/stdc++.h>
using namespace std;
int main(){
    int hp,NAtk,BAtk,sum=0;
    cin>>hp>>NAtk>>BAtk;
    if(hp<=NAtk)
        sum++;
    else if(hp<=BAtk)
        sum+=2;
    else if(2*NAtk>=BAtk){
        sum=hp/NAtk;
        if(hp%NAtk)
            sum++;
    }
    else{
        sum=hp/BAtk;
        int t=hp%BAtk;
        if(t!=0&&t<=NAtk)
            sum++;
        else if(t>NAtk)
            sum+=2;
    }
    cout<<sum;
    return 0;
}

发表于 2019-10-14 21:31:54 回复(0)
#include<stdio.h>
#include<iostream>
int main(){
    int HP,normalAttack,buffedAttack;
    scanf("%d",&HP);
    scanf("%d",&normalAttack);
    scanf("%d",&buffedAttack);
    int better=std::max(2*normalAttack,buffedAttack);
    int res=2*(HP/better);
    int remain=HP%better;

    res+=((int)(remain>normalAttack)+(int)(remain!=0));
    printf("%d",res);
    return 0;
}
说白了就是一个优先选择的问题
发表于 2019-09-29 21:21:30 回复(0)
分成四种情况:
import math
h = int(input())
n = int(input())
b = int(input())

if h // n == 0:
    print(1)
elif 2*n > b:
    print(math.ceil(h/n))
elif h%b > n or h%b == 0:
    print(math.ceil(h/b)*2)
else:
    print(math.ceil(h/b)*2-1)


运行时间:30ms
占用内存:3564k
发表于 2019-09-02 14:21:18 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int HP,x,y,cnt=0;
    cin>>HP>>x>>y;
    if(HP<=x)
        cout<<1<<endl;
    else{
        if((x<<1)>=y){
            cnt = int(ceil(1.0*HP/x));
        }else{
            while(HP>x){
                HP -= y;
                cnt += 2;
            }
            if(HP>0)
                cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

发表于 2019-08-23 00:08:07 回复(0)
dp递推会超内存,dp[i]=min(dp[i-normalAttack]+1, dp[i-buffedAttack]+2),即最后一次攻击使用normal还是buffed。
可以使用贪心思路来求解。normalAttack消耗一次攻击,造成normalAttack点伤害,buffedAttack消耗两次攻击,造成buffedAttack点伤害。
1.当血量n<=normal时,只需一次。
2.当血量高于normal时,需要判断normal*2和buffed的大小。若normal*2>=buffed,则每次均使用normal;若normal*2<buffed,优先使用buffed,当剩余血量小于normal时,判断剩余血量是否大于0,若大于0,最后一次使用normal即可。
#include<iostream>
#include<vector>
usingnamespacestd;
intmain()
{
    intn,k1,k2;
    cin>>n;
    cin>>k1;
    cin>>k2;
    if(n<=k1)
        cout<<1<<endl;//血量小于等于normal 一回合就能结束
    if(k1*2>=k2)//两次normal不小于一次Buff 只使用normal攻击
    {
        if(n%k1==0)
            cout<<n/k1<<endl;//整除 n/k1次
        else
            cout<<n/k1+1<<endl;//否则多攻击一次
    }
    else//buff比两次normal高 优先使用buff攻击 当剩余血量小于normal时 使用一次normal即可解决
    {
        intcnt=0;//记录总次数
        while(n>k1)//优先使用buff攻击
        {
            n-=k2;//剩余血量
            cnt+=2;//当前次数
        }
        if(n>0)
            cnt+=1;//剩余血量小于一次normal攻击 次数+1
        cout<<cnt<<endl;
    }
    return0;
}

编辑于 2019-07-27 12:23:29 回复(0)
"""
分支判断
"""
import math

if __name__ == "__main__":
    hp = int(input().strip())
    normalAttack = int(input().strip())
    buffedAttack = int(input().strip())
    ans = 0
    if 2 * normalAttack >= buffedAttack:
        ans = math.ceil(hp / normalAttack)
    else:
        ans = math.floor(hp / buffedAttack) * 2
        hp = hp % buffedAttack
        if hp > 0:
            if hp <= normalAttack:
                ans += 1
            else:
                ans += 2
    print(ans)

发表于 2019-07-17 22:03:46 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int hp,normalAttack,buffedAttack,res=0;
    cin>>hp;
    cin>>normalAttack;
    cin>>buffedAttack;
    if(normalAttack*2>buffedAttack)
    {
        if(hp%normalAttack==0)
            res=hp/normalAttack;
        else
            res=hp/normalAttack+1;
    }
    else
    {
        if(hp%buffedAttack==0)
            res=hp/buffedAttack*2;
        else if(hp%buffedAttack>normalAttack)
            res=hp/buffedAttack*2+2;
        else if(hp%buffedAttack<=normalAttack)
            res=hp/buffedAttack*2+1;
    }
    cout<<res<<endl;
    return 0;
}

发表于 2019-07-11 19:47:15 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    int hp,nA,bA;
    cin>>hp>>nA>>bA;
    int cnt1 = 0,cnt2 = 0,hp1 = hp;
    cnt1 += 2*(hp1 / bA);
    hp1 %=  bA;
    if(hp1 && hp1 <= nA) cnt1++;
    else if(hp1) cnt1 += 2;
    cnt2 += hp / nA;
    if(hp % nA) cnt2++;
    cout<<min(cnt1,cnt2)<<endl;
    return 0;
}
发表于 2019-12-03 16:29:09 回复(0)
            var hp=parseInt(readline());//血槽
            var normal=parseInt(readline());//物理攻击的伤害
            var bufferd=parseInt(readline());//使用魔法时的伤害
            // 还存在一个问题...可能魔法攻击伤害小于物理攻击(但是小于也不一定就一定不优先使用魔法,)
            //直接对物理*n,魔法*n都进行计算!
            //1.使用魔法为主
            var buf_num=Math.floor(parseInt(hp)/parseInt(bufferd));//魔法攻击次数
            var buf_yu_num=parseInt(hp)%parseInt(bufferd);//魔法时的余数
            var buf_nor_num=0;//魔法时的物理攻击次数
            if(buf_yu_num>normal){
                //可能物理攻击为2,魔法攻击是111,所以余数可能是物理攻击的倍数,此时就干脆魔法攻击一次(反正都是至少两回合),然后不使用物理攻击
                buf_nor_num=0
                buf_num++;
            }else if(buf_yu_num>0 && buf_yu_num<=normal){
                buf_nor_num=1;
            }
            var buf_all_num=buf_num*2+buf_nor_num;//魔法攻击为主时的攻击总次数
            
            //2.使用物理攻击为主
            var nor_num=Math.floor(parseInt(hp)/parseInt(normal));//物理攻击次数
            var nor_yu_num=parseInt(hp)%parseInt(normal);//物理时的余数
            var nor_buf_num=0;//物理时的魔法攻击次数
            // if(nor_yu_num/2>bufferd){
            //     //干脆再物理攻击一次
            //     nor_num++;
            //     nor_buf_num=0;
            // }else if(nor_yu_num>0 && nor_yu_num<bufferd){
            //     nor_buf_num=1;
            // }
//但是如果沦落到以物理攻击为主的地步,那么两次物理攻击一定大于一次魔法攻击,那么就一直使用物理攻击好了!
            if(nor_yu_num>0){
                nor_num++;
                nor_buf_num=0;
            }
            var nor_all_num=nor_num+nor_buf_num*2;//物理攻击为主时的攻击总次数
            print(nor_all_num>buf_all_num?buf_all_num:nor_all_num)

发表于 2019-12-02 23:07:34 回复(0)
var hp =readline();
var normalAttack = parseInt(readline());
var buffedAttack = parseInt(readline());
var count = 0;
if(normalAttack<(buffedAttack/2)){
    var t = parseInt(hp/buffedAttack);
    count = t*2;
    var y = hp%buffedAttack;
    if(y<=normalAttack&&y>0){
        count = count + 1;
    }else if(y>normalAttack){
        count = count+2;
    }
}else if(normalAttack>=(buffedAttack/2)){
    count = Math.ceil(hp/normalAttack)
}
print(count)

发表于 2019-09-08 12:12:26 回复(0)
h = int(input())
n = int(input())
b = int(input())

if b < 2 * n:
    if h % n != 0:
        print(h // n + 1)
    else:
        print(h // n)
else:
    y = h % b
    if y > n:
        print(2 * (h // b) + 2)
    elif y == 0:
        print(2 * (h // b))
    else:
        print(2 * (h // b) + 1)
发表于 2019-09-06 17:09:52 回复(0)
hp = int(input())
normal_attack = int(input())
buffered_attack = int(input())
if buffered_attack <= 2 * normal_attack:
    print((hp-1) // normal_attack + 1)
else:
    nums_buf = (hp-1) // buffered_attack 
    end = hp % buffered_attack
    if end == 0:
        nums_buf += 1
        print(2*nums_buf)
    elif end <= normal_attack:
        print(2*nums_buf + 1)
    else:
        nums_buf += 1
        print(2*nums_buf)
发表于 2019-09-06 15:12:46 回复(0)
HP=int(input())
normal=int(input())
buffed=int(input())
if 2*normal>=buffed:
    if HP%normal==0:
        print(HP//normal)
    else:
        print(HP//normal+1)
else:
    if HP%buffed==0:
        print(2*HP//buffed)
    else:
        print(2*HP//buffed+1)

发表于 2019-09-01 11:09:34 回复(0)
#include <iostream>
using namespace std;
int main(void){
    int HP, normalAttack, buffedAttack, count;
    cin>>HP>>normalAttack>>buffedAttack;
    if(HP <= normalAttack){
        cout<<1<<endl;
        return 0;
    }
    if(normalAttack*2 >= buffedAttack){
        cout<<(HP/normalAttack + (HP%normalAttack ? 1 : 0))<<endl;
    }else{
        cout<<(HP/buffedAttack*2 + (!(HP%buffedAttack) ? 0 : HP%buffedAttack > normalAttack ? 2 : 1))<<endl;    
    }
    return 0;
}
加成攻击小于等于普通攻击的2倍时,一直使用普通攻击,血量没有整除普通攻击的话回合数加1
加成攻击大于普通攻击的2倍时,一直使用加成攻击,血量没有整除加成攻击的话判断剩余血量和普通攻击的关系,剩余血量小于等于普通攻击回合数加1,否则加2在进行一次加成攻击
注意:结果和HP%attack有关,尤其是buffedAttack,有三种情况要判断
编辑于 2019-08-19 10:02:55 回复(0)
#include <iostream>
using namespace std;
int main(){
    int HP, nA, bA;
    cin>>HP>>nA>>bA;
    int num=0;
    if (bA<=2*nA){
        while(HP>0){
            num++;
            HP-=nA;
        }
    } else {
        while (HP>0){
            if (HP<=nA){
                num++;
                HP-=nA;
            } else {
                num+=2;
                HP-=bA;
            }
        }
    }
    cout<<num<<endl;
    return 0;
}

发表于 2019-08-16 14:16:09 回复(0)
hp = int(input())
na = int(input())
ba = int(input())
if ba <= na*2:
    if hp%na == 0:
        print(hp//na)
    else:print(hp//na+1)
else:
    n = hp//ba
    m = hp%ba
    if m == 0:
        print(2*n)
    elif m != 0 and m<=na:
        print(n*2+1)
    else:
        print(n*2+2)

发表于 2019-08-15 17:02:31 回复(0)
DP超时,过90%
#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
int main(){
    int sum, na, ba;
    scanf("%d%d%d", &sum, &na, &ba);
    int ppre = sum, pre = sum-na, cur;
    for(int i=2; i<sum; i++){
        cur = min(ppre-ba, pre-na);
        ppre = pre;
        pre = cur;
        if(cur<=0){
            printf("%d\n", i);
            return 0;
        }
    }
    return 0;
}

发表于 2019-07-28 13:53:20 回复(0)
import math
def min_round(hp, norm, high):
    if norm * 2 >= high:
        return math.ceil(hp / norm)
    else:
        r = hp % high 
        if r == norm:
            return math.ceil(hp / high) * 2 - 1
        return math.ceil(hp / high) * 2
1. if 2倍普通攻击>=强化攻击,返回全部使用普通攻击的回合数
2. else 判断剩余血量使用普通攻击是否能一次结束,yes 返回全部使用强化攻击回合数-1,no 返回全部使用强化攻击回合数
发表于 2019-07-28 05:48:41 回复(0)