首页 > 试题广场 > 回合制游戏
[编程题]回合制游戏
  • 热度指数:6474 时间限制: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 回复(4)
很简洁的写法
import java.util.Scanner;

public class No4BuffAttack {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
            int HP = scanner.nextInt();
            int normal = scanner.nextInt();
            int buff = scanner.nextInt();
            if (buff<=2*normal)  //如果buff小于两倍normal,一直用normal攻击是最划算的
                System.out.println(HP%normal==0?HP/normal:HP/normal+1);
            else {//如果buff高,那么先用buff进行攻击
                int left=HP%buff;  //取余,判断最后的血量用什么来攻击
                if (left==0)  //如果血量为零,说明一直用buff来攻击就可以了
                    System.out.println(HP/buff*2); 
                else if (left<=normal)//如果余量小于normal,说明最后一次的攻击用normal是最好的
                    System.out.println(HP/buff*2+1);
                else System.out.println(HP/buff*2+2);
            }
            return;
    }
}


发表于 2020-02-21 10:36:41 回复(0)
用数学方法进行求解:
由于蓄力攻击一次需要两个回合,因此只有当蓄力攻击的威力大于等于普通攻击两倍的时候,才优先使用蓄力攻击,否则就使用普通攻击。如果使用蓄力攻击的话需要考虑敌人在若干次蓄力攻击后的剩余血量(不等于一次蓄力攻击或者普通攻击造成的伤害),如果剩余血量一次普通攻击就能带走就还需要一个回合,否则还需要两个回合。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long HP = Long.parseLong(br.readLine().trim());
        long normalAttack = Long.parseLong(br.readLine().trim());
        long buffedAttack = Long.parseLong(br.readLine().trim());
        if(2*normalAttack > buffedAttack){
            // 此时不使用蓄力
            System.out.println((HP + normalAttack - 1)/normalAttack);
        }else{
            // 此时蓄力之后的打击更强
            long times = HP/buffedAttack*2;
            long remain = HP % buffedAttack;      // 蓄力攻击若干次后的剩余血量
            if(remain <= normalAttack){
                // 此时剩余的血量用一次普通攻击就能带走
                if(remain > 0) times ++;
            }else{
                // 此时的血量需要用到蓄力才能带走,还需要两个回合
                times += 2;
            }
            System.out.println(times);
        }
    }
}


编辑于 2021-02-01 09:36:37 回复(0)
Java 的解法, 比较简短, 没啥好说的: 这题数字比较大, 注意用 除法 而非 乘法来防止数字溢出, 算法很容易, 复杂度 O(1)/O(1)
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int HP = scan.nextInt();
        int atk = scan.nextInt(), batk = scan.nextInt();
        // 核心算法部分:
        if(batk/2 >= atk) {
            int r = HP % (batk);
            int c = HP / batk * 2;
            if(r == 0) {
                System.out.println(c);
            } else {
                System.out.println(c + (r <= atk? 1: 2));
            }
        } else {
            System.out.println((int)Math.ceil((HP + 0.0) / atk));
        }
    }
}


发表于 2020-03-20 11:16:37 回复(0)
package 回合制游戏;

import java.util.Scanner;

/*
 * 你在玩一个回合制角色扮演的游戏。
 * 现在你在准备一个策略,以便在最短的回合内击败敌方角色。
 * 在战斗开始时,敌人拥有HP格血量。当血量小于等于0时,敌人死去。
 * 一个缺乏经验的玩家可能简单地尝试每个回合都攻击。但是你知道辅助技能的重要性。
 * 在你的每个回合开始时你可以选择以下两个动作之一:聚力或者攻击。
 * 聚力会提高你下个回合攻击的伤害。
 * 攻击会对敌人造成一定量的伤害。如果你上个回合使用了聚力,那这次攻击会对敌人造成buffedAttack点伤害。
 * 否则,会造成normalAttack点伤害。
 * 给出血量HP和不同攻击的伤害,buffedAttack和normalAttack,返回你能杀死敌人的最小回合数。
 * 
 * 输入描述:
 * 第一行是一个数字HP
 * 第二行是一个数字normalAttack
 * 第三行是一个数字buffedAttack
 * 1 <= HP,buffedAttack,normalAttack <= 10^9
 * 
 * 输出描述:
 * 输出一个数字表示最小回合数
 * 
 * 输入例子1:
 * 13
 * 3
 * 5
 * 
 * 输出例子1:
 * 5
 */
/*
 * 算法:贪心
 * 数据结构:基本数据类型
 * 思路:如果buffedAttack <= 2 * normalAttack,则一直使用普通攻击;
 * 如果buffedAttack > 2 * normalAttack,一定优先使用加强攻击;
 * 若healthPoint % 2 != 0,则存在最后一击的选择;
 * 最后一击<=normalAttack,则最后一击使用普通攻击,否则还是使用加强攻击。
 */
public class Main {
	
	//一直使用普通攻击时的回合数
	private static int getRoundAlwaysNormalAttack(int healthPoint, int normalAttack, int buffedAttack) {
		int round = 0;
		//向上取整
		if (healthPoint % normalAttack == 0) {
			round = healthPoint / normalAttack;
		}
		else {
			round = healthPoint / normalAttack + 1;
		}
		return round;
	}
	
	//优先使用加强攻击时的回合数
	private static int getRoundPriorityBuffedAttack(int healthPoint, int normalAttack, int buffedAttack) {
		int round = 0;
		//不存在最后一击的选择
		if (healthPoint % buffedAttack == 0) {
			round = 2 * (healthPoint / buffedAttack);
		}
		else if (healthPoint % buffedAttack <= normalAttack) {
			round = 2 * (healthPoint / buffedAttack) + 1;
		}
		else {
			//healthPoint / buffedAttack保证次数准确,不能被*2影响,最先运算
			round = 2 * (healthPoint / buffedAttack) + 2;
		}
		return round;
	}
	
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int healthPoint = input.nextInt();
		int normalAttack = input.nextInt();
		int buffedAttack = input.nextInt();
		input.close();
		
		int minRound = 0;
		if (buffedAttack <= 2 * normalAttack) {
			minRound = getRoundAlwaysNormalAttack(healthPoint, normalAttack, buffedAttack);
		}
		else {
			minRound = getRoundPriorityBuffedAttack(healthPoint, normalAttack, buffedAttack);
		}
		System.out.println(minRound);
	}
}

发表于 2020-03-10 10:41:48 回复(0)
#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)
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)
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 <cstdio>
using namespace std;
int main(){
    int HP,normalAttack,buffedAttack,num;
    scanf("%d",&HP);
    scanf("%d",&normalAttack);
    scanf("%d",&buffedAttack);
    if(buffedAttack>=(2*normalAttack)) {
    int yu=HP%buffedAttack;
    num=(HP/buffedAttack)*2; //重击回合数 
    num+=((yu-1)/normalAttack+1);  //最小回合数 
	}else{
		num=(HP-1)/normalAttack+1;
	}
	printf("%d",num);
}
大佬们,我测几组数据包括这个网站给出的数据都测了,都是正确的,为什么这个编译器答案和我在别的编译器上的结果不一致
发表于 2020-11-11 17:24:07 回复(0)
     动态规划---只A了90%,好像内存溢出了
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int hp = scanner.nextInt();
        int normalAttack = scanner.nextInt();
        int buffedAttack = scanner.nextInt();
        int max_n = hp/normalAttack + 1;
        int max_b = (hp/normalAttack + 1) * 2;
        int max = Math.max(max_b,max_n);
        if(Math.min(max_b,max_n) <= 1){
            System.out.println(1);
            return;
        }
        int [][] dp = new int[max][2];
 
        dp[0][0] = 0;
        dp[0][1] = 0;
        dp[1][0] = normalAttack;
        dp[1][1] = 0;
        int i = 2;
        while (true){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]) + normalAttack;
            dp[i][1] = Math.max(dp[i-2][0], dp[i-2][1]) + buffedAttack;
            if(Math.max(dp[i][0], dp[i][1]) >= hp){
                System.out.println(i);
                return;
            }
            i++;
        }
    }
}


发表于 2020-09-01 15:09:04 回复(0)
def helper(t, s, b):
    if t <= 0:
        return 0
     
    if s >= t:
        return 1
     
    if b <= 2 * s:
        if t % s:
            return t // s + 1
        else:
            return t // s
     
    if b > 2 * s:
        res = t % b
        if res:
            base = t // b * 2
            t = res
            return base + min(1 + helper(t - s, s, b), 2 + helper(t - b, s, b))
        else:
            return t // b * 2
     
    return 
 
total = int(input())
small = int(input())
big = int(input())
 
print(helper(total, small, big))

发表于 2020-08-01 17:17:50 回复(0)
.n9头像 .n9
HP, nA, bA = int(input()), int(input()), int(input())
print((HP + nA - 1) // nA if nA * 2 >= bA else HP // bA * 2 + (1 + (HP % bA > nA)) * (HP % bA > 0))

发表于 2020-07-14 17:01:25 回复(0)
hp = int(input())

n = int(input())
b = int(input())

if b <= 2*n:
    if hp % n == 0:
        print(hp // n)
    else:
        print(hp // n + 1)
else:
    if hp % b == 0:
        print(hp // b *2)
    elif 0< hp % b <= n:
        print(hp // b *2 + 1)
    else:
        print(hp // b *2 + 2)

发表于 2020-06-30 16:44:55 回复(0)
别想复杂了,就简单的数学问题啊
#include <iostream>
using namespace std;

int main(int argc, char* argv[]){
    int hp, normal, buffered;
    cin >> hp >> normal >> buffered;
    if(2*normal >= buffered) cout << (hp+normal-1)/normal << endl;
    else {
        int round = hp/buffered, rest = hp - round*buffered;
        if(rest == 0) cout << round*2 << endl;
        else if(rest <= normal) cout << round*2 + 1 << endl;
        else cout << round*2+2 << endl;
    }
    return 0;
}


编辑于 2020-05-14 08:41:01 回复(0)