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]intvar 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;}
复制代码
评论