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完整代码如下：
packagemain
import(
"fmt"
)
constMAXN=11
varkill[MAXN]int
varblood[MAXN]int
funcmain(){
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++
fori:=0;in:=inputs[ii]
ii++
m:=inputs[ii]
ii++
forj:=0;jkill[j]=inputs[ii]
ii++
blood[j]=inputs[ii]
ii++
}
ans:=f(n,0,m)
ifans==int(^uint(0)>>1){
fmt.Println(-1)
}else{
fmt.Println(ans)
}
}
}
funcf(n,i,restint)int{
ifrest<=0{
returni
}
ifi==n{
returnint(^uint(0)>>1)
}
ans:=int(^uint(0)>>1)
forj:=i;jswap(i,j)
ifrest>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)
}
returnans
}
funcswap(i,jint){
kill[i],kill[j]=kill[j],kill[i]
blood[i],blood[j]=blood[j],blood[i]
}
funcmin(a,bint)int{
ifareturna
}
returnb
}
rust完整代码如下：
constMAXN:usize=11;
staticmutKILL:[i32;MAXN]=[0;MAXN];
staticmutBLOOD:[i32;MAXN]=[0;MAXN];
fnmain(){
letinputs=[
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,
];
letmutii=0;
lett=inputs[iiasusize];
ii+=1;
for_in0..t{
letn=inputs[iiasusize];
ii+=1;
letm=inputs[iiasusize];
ii+=1;
unsafe{
forjin0..n{
KILL[jasusize]=inputs[iiasusize];
ii+=1;
BLOOD[jasusize]=inputs[iiasusize];
ii+=1;
}
}
letans=f(n,0,m);
ifans==std::i32::MAX{
println!("-1");
}else{
println!("{}",ans);
}
}
}
fnf(n:i32,i:i32,rest:i32)->i32{
ifrest<=0{
returniasi32;
}
ifi==n{
returnstd::i32::MAX;
}
unsafe{
letmutans=std::i32::MAX;
forjini..n{
swap(i,j);
ifrest>BLOOD[iasusize]{
ans=min(ans,f(n,i+1,rest-KILL[iasusize]));
}else{
ans=min(ans,f(n,i+1,rest-KILL[iasusize]*2));
}
swap(i,j);
}
ans
}
}
fnswap(i:i32,j:i32){
unsafe{
lettemp_k=KILL[iasusize];
lettemp_b=BLOOD[iasusize];
KILL[iasusize]=KILL[jasusize];
BLOOD[iasusize]=BLOOD[jasusize];
KILL[jasusize]=temp_k;
BLOOD[jasusize]=temp_b;
}
}
fnmin(a:i32,b:i32)->i32{
ifaa
}else{
b
}
}
c++完整代码如下：
#include
#include
usingnamespacestd;
constintMAXN=11;
intkill[MAXN];
intblood[MAXN];
intf(intn,inti,intrest){
if(rest<=0){
returni;
}
if(i==n){
returnINT_MAX;
}
intans=INT_MAX;
for(intj=i;jswap(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]);
}
returnans;
}
intmain(){
intinputs[]={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};
intii=0;
intt=inputs[ii++];
for(inti=0;iintn=inputs[ii++];
intm=inputs[ii++];
for(intj=0;jkill[j]=inputs[ii++];
blood[j]=inputs[ii++];
}
intans=f(n,0,m);
if(ans==INT_MAX){
cout<<-1<}
else{
cout<}
}
return0;
}
c完整代码如下：
#include
#include
#defineMAXN11
intkill[MAXN];
intblood[MAXN];
intmin(inta,intb){
return(a}
voidswap(int*a,int*b){
inttemp=*a;
*a=*b;
*b=temp;
}
intf(intn,inti,intrest){
if(rest<=0){
returni;
}
if(i==n){
returnINT_MAX;
}
intans=INT_MAX;
for(intj=i;jswap(&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]);
}
returnans;
}
intmain(){
intinputs[]={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};
intii=0;
intt=inputs[ii++];
for(inti=0;iintn=inputs[ii++];
intm=inputs[ii++];
for(intj=0;jkill[j]=inputs[ii++];
blood[j]=inputs[ii++];
}
intans=f(n,0,m);
if(ans==INT_MAX){
printf("%d\n",-1);
}
else{
printf("%d\n",ans);
}
}
return0;
}
热门跟贴