2024-01-13:用go语言,现在有一个打怪类型的游戏,这个游戏是这样的

2024-01-13:用go语言,现在有一个打怪类型的游戏,这个游戏是这样的,你有n个技能,

每一个技能会有一个伤害,

同时若怪物小于等于一定的血量,则该技能可能造成双倍伤害,

每一个技能最多只能释放一次,已知怪物有m点血量。

现在想问你最少用几个技能能消灭掉他(血量小于等于0)。

技能的数量是n,怪物的血量是m,

i号技能的伤害是x[i],i号技能触发双倍伤害的血量最小值是y[i]。

1 <= n <= 10,

1 <= m、x[i]、y[i] <= 10^6。

答案2024-01-13:

来自左程云

灵捷3.5

大体过程如下:

1.读取输入数据,包括技能数量 n、怪物血量 m,以及每个技能的伤害和触发双倍伤害的血量阈值。

2.定义一个递归函数 f(n, i, rest) 来求解最少使用多少个技能能够消灭怪物。其中,n 表示当前剩余的技能数量,i 表示当前考虑的技能索引,rest 表示剩余的怪物血量。

3.在递归函数 f 中,先判断如果剩余血量 rest 小于等于 0,则返回当前已使用技能的数量 i,表示已经成功消灭怪物。

4.继续判断如果技能索引 i 等于技能数量 n,则说明已经考虑完所有技能,但仍无法消灭怪物,返回一个较大的数值作为无解情况的标识。

5.初始化一个变量 ans 为一个较大的数值,用于记录最小使用技能数量。然后进入循环,从第 i 个技能开始尝试使用不同的技能。

6.在循环中,交换第 i 个技能和当前技能索引 j 对应的技能,以模拟尝试使用该技能。

7.判断如果剩余血量 rest 大于当前技能要求的血量触发双倍伤害的阈值 blood[i],则调用递归函数 f(n, i+1, rest-kill[i]),即不使用双倍伤害的情况下消灭怪物。

8.否则,调用递归函数 f(n, i+1, rest-kill[i]*2),即使用双倍伤害的情况下消灭怪物。

9.根据递归函数返回的结果,更新 ans 的最小值。

10.恢复交换前的技能顺序,保持数组的原始状态。

11.循环结束后,返回 ans 作为最终的结果。

总的时间复杂度为 O(n!),因为要求所有可能的技能使用组合。

额外空间复杂度为 O(n),主要是递归调用栈的空间。

go完整代码如下:

package main

import (
    "fmt"
)

const MAXN = 11

var kill [MAXN]int
var blood [MAXN]int

func main() {
    inputs := []int{3,
        3, 100,
        10, 20,
        45, 89,
        5, 40,
        3, 100,
        10, 20,
        45, 90,
        5, 40,
        3, 100,
        10, 20,
        45, 84,
        5, 40}
    ii := 0
    t := inputs[ii]
    ii++
    for i := 0; i < t; i++ {
        n := inputs[ii]
        ii++
        m := inputs[ii]
        ii++
        for j := 0; j < n; j++ {
            kill[j] = inputs[ii]
            ii++
            blood[j] = inputs[ii]
            ii++
        }
        ans := f(n, 0, m)
        if ans == int(^uint(0)>>1) {
            fmt.Println(-1)
        } else {
            fmt.Println(ans)
        }
    }

}

func f(n, i, rest int) int {
    if rest <= 0 {
        return i
    }
    if i == n {
        return int(^uint(0) >> 1)
    }
    ans := int(^uint(0) >> 1)
    for j := i; j < n; j++ {
        swap(i, j)
        if rest > blood[i] {
            ans = min(ans, f(n, i+1, rest-kill[i]))
        } else {
            ans = min(ans, f(n, i+1, rest-kill[i]*2))
        }
        swap(i, j)
    }
    return ans
}

func swap(i, j int) {
    kill[i], kill[j] = kill[j], kill[i]
    blood[i], blood[j] = blood[j], blood[i]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

在这里插入图片描述

rust完整代码如下:

const MAXN: usize = 11;

static mut KILL: [i32; MAXN] = [0; MAXN];
static mut BLOOD: [i32; MAXN] = [0; MAXN];

fn main() {
    let inputs = [
        3, 3, 100, 10, 20, 45, 89, 5, 40, 3, 100, 10, 20, 45, 90, 5, 40, 3, 100, 10, 20, 45, 84, 5,
        40,
    ];

    let mut ii = 0;
    let t = inputs[ii as usize];
    ii += 1;

    for _ in 0..t {
        let n = inputs[ii as usize];
        ii += 1;
        let m = inputs[ii as usize];
        ii += 1;

        unsafe {
            for j in 0..n {
                KILL[j as usize] = inputs[ii as usize];
                ii += 1;
                BLOOD[j as usize] = inputs[ii as usize];
                ii += 1;
            }
        }

        let ans = f(n, 0, m);
        if ans == std::i32::MAX {
            println!("-1");
        } else {
            println!("{}", ans);
        }
    }
}

fn f(n: i32, i: i32, rest: i32) -> i32 {
    if rest <= 0 {
        return i as i32;
    }

    if i == n {
        return std::i32::MAX;
    }

    unsafe {
        let mut ans = std::i32::MAX;

        for j in i..n {
            swap(i, j);

            if rest > BLOOD[i as usize] {
                ans = min(ans, f(n, i + 1, rest - KILL[i as usize]));
            } else {
                ans = min(ans, f(n, i + 1, rest - KILL[i as usize] * 2));
            }

            swap(i, j);
        }

        ans
    }
}

fn swap(i: i32, j: i32) {
    unsafe {
        let temp_k = KILL[i as usize];
        let temp_b = BLOOD[i as usize];

        KILL[i as usize] = KILL[j as usize];
        BLOOD[i as usize] = BLOOD[j as usize];

        KILL[j as usize] = temp_k;
        BLOOD[j as usize] = temp_b;
    }
}

fn min(a: i32, b: i32) -> i32 {
    if a < b {
        a
    } else {
        b
    }
}

在这里插入图片描述

c++完整代码如下:

#include <iostream>
#include <limits.h>
using namespace std;

const int MAXN = 11;

int kill[MAXN];
int blood[MAXN];

int f(int n, int i, int rest) {
    if (rest <= 0) {
        return i;
    }
    if (i == n) {
        return INT_MAX;
    }
    int ans = INT_MAX;
    for (int j = i; j < n; j++) {
        swap(kill[i], kill[j]);
        swap(blood[i], blood[j]);
        if (rest > blood[i]) {
            ans = min(ans, f(n, i + 1, rest - kill[i]));
        }
        else {
            ans = min(ans, f(n, i + 1, rest - kill[i] * 2));
        }
        swap(kill[i], kill[j]);
        swap(blood[i], blood[j]);
    }
    return ans;
}

int main() {
    int inputs[] = { 3,
                    3, 100,
                    10, 20,
                    45, 89,
                    5, 40,
                    3, 100,
                    10, 20,
                    45, 90,
                    5, 40,
                    3, 100,
                    10, 20,
                    45, 84,
                    5, 40 };
    int ii = 0;
    int t = inputs[ii++];
    for (int i = 0; i < t; i++) {
        int n = inputs[ii++];
        int m = inputs[ii++];
        for (int j = 0; j < n; j++) {
            kill[j] = inputs[ii++];
            blood[j] = inputs[ii++];
        }
        int ans = f(n, 0, m);
        if (ans == INT_MAX) {
            cout << -1 << endl;
        }
        else {
            cout << ans << endl;
        }
    }
    return 0;
}

在这里插入图片描述

c完整代码如下:

#include <stdio.h>
#include <limits.h>

#define MAXN 11

int kill[MAXN];
int blood[MAXN];

int min(int a, int b) {
    return (a < b) ? a : b;
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int f(int n, int i, int rest) {
    if (rest <= 0) {
        return i;
    }
    if (i == n) {
        return INT_MAX;
    }
    int ans = INT_MAX;
    for (int j = i; j < n; j++) {
        swap(&kill[i], &kill[j]);
        swap(&blood[i], &blood[j]);
        if (rest > blood[i]) {
            ans = min(ans, f(n, i + 1, rest - kill[i]));
        }
        else {
            ans = min(ans, f(n, i + 1, rest - kill[i] * 2));
        }
        swap(&kill[i], &kill[j]);
        swap(&blood[i], &blood[j]);
    }
    return ans;
}

int main() {
    int inputs[] = { 3,
                    3, 100,
                    10, 20,
                    45, 89,
                    5, 40,
                    3, 100,
                    10, 20,
                    45, 90,
                    5, 40,
                    3, 100,
                    10, 20,
                    45, 84,
                    5, 40 };
    int ii = 0;
    int t = inputs[ii++];
    for (int i = 0; i < t; i++) {
        int n = inputs[ii++];
        int m = inputs[ii++];
        for (int j = 0; j < n; j++) {
            kill[j] = inputs[ii++];
            blood[j] = inputs[ii++];
        }
        int ans = f(n, 0, m);
        if (ans == INT_MAX) {
            printf("%d\n", -1);
        }
        else {
            printf("%d\n", ans);
        }
    }
    return 0;
}

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 1

哦, 你懂得语言真多 :joy:

1个月前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
455
粉丝
21
喜欢
37
收藏
22
排名:465
访问:1.9 万
私信
所有博文
社区赞助商