首页 > 试题广场 > 回合制游戏
[编程题]回合制游戏
你在玩一个回合制角色扮演的游戏。现在你在准备一个策略,以便在最短的回合内击败敌方角色。在战斗开始时,敌人拥有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 回复(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 <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)
def minRounds(Hp,nA,bA):
    if bA<=2*nA:
        return (Hp-1)//nA+1
    else:
        if Hp%bA<=nA and Hp%bA!=0:
            return (2*(Hp//bA)+1)
        else:
            if Hp%bA==0:
                return (2*(Hp//bA))
            else:
                return (2*(Hp//bA+1))
 
Hp,nA,bA=int(raw_input()),int(raw_input()),int(raw_input())
print minRounds(Hp,nA,bA)

发表于 2019-07-27 20:52:12 回复(0)

优化加深度优先最多90%
buffee/ normal>2时毫无疑问多选择buffedattacked

#include<bits/stdc++.h>
using namespace std;
void dfs(int hp , const int& buffed,const int& normal,int& count,int cnt)
{
    if(hp>normal && hp<=buffed)
    {
        count=min(count,cnt+2);
        return ;
    }
    if(hp>0 && hp<=normal)
    {
        count=min(count,cnt+1);
        return ;
    }
    dfs(hp-buffed,buffed,normal,count,cnt+2);
    dfs(hp-normal,buffed,normal,count,cnt+1);
}
int main()
{
    int hp;
    cin>>hp;
    int buffed=0,normal=0;
    cin>>normal>>buffed;
    int count=INT_MAX;
    if(hp<normal)
    {
        cout<<1<<endl;
    }
    else if(hp<=buffed && hp>normal)
    {
        cout<<2<<endl;
    }
    else if(buffed/normal>=2)
    {
        int a=hp-hp/buffed *buffed;
        int b=0;
        if(a>0)
            b= a<=normal ? 1 :2;
        cout<<(hp/buffed*2+b)<<endl;
    }
    else if(buffed/normal<2 )
    {
        dfs(hp,buffed,normal,count,0);
        cout<<count<<endl;
    }
    return 0;
}
发表于 2019-07-27 19:15:23 回复(0)

1、能基本攻击,就基本攻击
2、能蓄力,就蓄力
3、如果基本攻击*2>=蓄力,就基本攻击;否则,就蓄力

importjava.util.Scanner;
publicclassMain {
    publicstaticvoidmain(String[] args){
        Scanner in=newScanner(System.in);
        inthp=in.nextInt();
        intnomalAttack=in.nextInt();
        intbuffedAttack=in.nextInt();
        intstep=0;
        while(hp>0){
            if(hp<=nomalAttack){
                ++step;
                break;
            }
            if(hp<=buffedAttack){
                step+=2;
                break;
            }
            if(nomalAttack*2>=buffedAttack){
                step+=hp/nomalAttack;
                hp%=nomalAttack;
            }else{
                step+=hp/buffedAttack*2;
                hp%=buffedAttack;
            }
        }
        System.out.println(step);
    }
}
发表于 2019-07-27 18:05:54 回复(0)
hp = int(input())
normalattack = int(input())
buffedattack = int(input())
ans = 0
if buffedattack >= 2 * normalattack:
    if 0 == hp % buffedattack:
        ans += hp // buffedattack * 2
    elif hp % buffedattack > normalattack:
        ans += hp // buffedattack * 2 + 2
    else:
        ans += hp // buffedattack * 2 + 1
elif buffedattack < 2 * normalattack and 0 == hp % normalattack:
    ans += hp // normalattack
else:
    ans += hp // normalattack + 1
print(ans)

发表于 2019-07-25 13:55:43 回复(0)
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int Hp=sc.nextInt();
        int n=sc.nextInt();
        int b=sc.nextInt();
        if(b>=2*n){
            System.out.println((Hp%b>n?2:(Hp%b)==0?0:1)+(Hp/b)*2);
        }else {
            System.out.println(Hp%n==0?Hp/n:(Hp/n)+1);
        } 
    }
}

发表于 2019-07-19 17:26:11 回复(0)
公司估计是想通过这道题给公司内部的峡谷吸收点具备游戏常识的人员,毕竟写代码很枯燥。没事不去峡谷转下,岂不是妄负少白头!
#include <iostream>
#include <algorithm>
#include <vector>
usingnamespacestd;
intmain()
{
    intnum;
    while(cin >> num)//读入元素的总个数
    {
        intHp = num;
        intnormalAttack;
        intHighAtacck;
        cin >> normalAttack;
        cin >> HighAtacck;
        if(normalAttack*2>=HighAtacck)
        {
            if(Hp%normalAttack==0)
            {
                cout << Hp / normalAttack;
            }
            else
            {
                cout << Hp / normalAttack + 1;
            }      
        }
        else
        {
            if(Hp%HighAtacck>normalAttack)
            {
                cout << (Hp / HighAtacck) * 2 + 2;
            }
            else
            {
                if(Hp%HighAtacck==0)
                {
                    cout << (Hp / HighAtacck) * 2 ;
                }
                else
                {
                      cout << (Hp / HighAtacck) * 2 + 1;
                }
                 
            }      
        }
    }  
    system("PAUSE");
    return0;
}

发表于 2019-06-12 21:16:55 回复(0)
import java.util.*;
 
public class Main{
 
  publicstaticvoidmain(String[] args) {
 
      Scanner scanner = newScanner(System.in);
 
      int hp = scanner.nextInt(); //总血量
 
      int normal = scanner.nextInt(); //正常伤害
 
      int buffer = scanner.nextInt(); //蓄力伤害
 
      int normalCount = (hp % normal == 0)? hp / normal :hp / normal + 1;
 
      int bufferCount = (hp % buffer <= normal)?2*(hp / buffer):2*(hp / buffer +1);  //当余数大于正常伤害时则还是需要两次攻击,余数等于0时直接结束,但是余数大于0小于正常伤害,攻击需+1
 
      if(normalCount <= bufferCount)
 
          System.out.println(normalCount);
 
      elseif(bufferCount < normalCount && hp % buffer !=0&& hp % buffer<=normal){//剔除特例:hp%huffer的余数不为0且比normal小,此时,次数需要加1
 
          System.out.println(bufferCount+1);
 
      }else{
 
          System.out.println(bufferCount);
 
      }
                                            
   }
 
}

发表于 2019-04-25 12:07:33 回复(0)