求解思路
这道题采用全排列枚举加递归回溯的思想，通过交换技能位置来尝试所有可能的使用顺序。
递归函数 f(n, i, r) 表示有n个技能、当前考虑第i个位置、怪物剩余血量为r时最少需要多少个技能才能击杀。
当怪物血量降至0以下时返回已使用的技能数，当技能用完但怪物仍存活则返回无效值 Integer.MAX_VALUE。
核心逻辑是在每个位置枚举将后面哪个技能交换到当前位置使用，根据怪物当前血量与技能阈值的关系计算伤害（血量大于阈值造成普通伤害，否则双倍），然后递归求解后续状态，通过 Math.min 不断更新最优解，最后通过回溯恢复现场以便尝试其他排列方案。
完整实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main{
// 最大技能数量
public static int MAXN = 11;
// kill[i]：第i个技能的伤害值
public static int[] kill = new int[MAXN];
// blood[i]：第i个技能的血量阈值
public static int[] blood = new int[MAXN];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
// 读取测试用例数量
while (in.nextToken() != StreamTokenizer.TT_EOF) {
int t = (int) in.nval;
// 处理每个测试用例
for (int i = 0; i < t; i++) {
in.nextToken();
int n = (int) in.nval; // 技能数量
in.nextToken();
int m = (int) in.nval; // 怪物初始血量
// 读取每个技能的属性
for (int j = 0; j < n; j++) {
in.nextToken();
kill[j] = (int) in.nval; // 伤害值
in.nextToken();
blood[j] = (int) in.nval; // 血量阈值
}
// 求解并输出结果
int ans = f(n, 0, m);
out.println(ans == Integer.MAX_VALUE ? -1 : ans);
}
}
out.flush();
br.close();
out.close();
}
public static int f(int n, int i, int r) {
// 基础情况1：怪物已死亡
if (r <= 0) {
return i; // 返回已使用的技能数
}
// 基础情况2：技能用完但怪物还活着
if (i == n) {
return Integer.MAX_VALUE; // 无效方案
}
// 尝试所有可能的技能排列
int ans = Integer.MAX_VALUE;
for (int j = i; j < n; j++) {
// 将第j个技能交换到第i个位置
swap(i, j);
// 计算使用当前技能后的伤害
// 如果怪物血量 > 阈值，造成普通伤害；否则造成双倍伤害
int damage = r > blood[i] ? kill[i] : kill[i] * 2;
// 递归计算后续最优解
ans = Math.min(ans, f(n, i + 1, r - damage));
// 回溯：恢复原状态
swap(i, j);
}
return ans;
}
public static void swap(int i, int j) {
int tmp = kill[i];
kill[i] = kill[j];
kill[j] = tmp;
tmp = blood[i];
blood[i] = blood[j];
blood[j] = tmp;
}
}
|
如果觉得有帮助，欢迎点赞、关注、转发~