rust 2022-11-09：给定怪兽的血量为hp 第i回合如果用刀砍，怪兽在这回合会直接掉血，没有后续效果 第i回合如果用毒，怪兽在这回合不会掉血， 但是之后每回合都会掉血，并且所有中毒的后续效果会叠加 给

2022-11-09：给定怪兽的血量为hp 第i回合如果用刀砍，怪兽在这回合会直接掉血，没有后续效果 第i回合如果用毒，怪兽在这回合不会掉血， 但是之后每回合都会掉血，并且所有中毒的后续效果会叠加 给定的两个数组cuts、poisons，两个数组等长，长度都是n 表示你在n回合内的行动， 每一回合的刀砍的效果由cuts[i]表示 每一回合的中毒的效果由poisons[i]表示 如果你在n个回合内没有直接杀死怪兽，意味着你已经无法有新的行动了 但是怪兽如果有中毒效果的话，那么怪兽依然会在hp耗尽的那回合死掉。 返回你最快能在多少回合内将怪兽杀死。 数据范围 : 1 <= n <= 10的5次方 1 <= hp <= 10的9次方 1 <= cuts[i]、poisons[i] <= 10的9次方。

答案2022-11-09：

二分答案法。 时间复杂度：O(N * log(hp))。 额外空间复杂度：O(1)。

代码用rust编写。代码如下：

use rand::Rng;

use std::iter::repeat;

fn main() {

let nn: i32 = 30;

let cut_v = 20;

let posion_v = 10;

let hp_v = 200;

let test_time: i32 = 10000;

println!("测试开始");

for i in 0..test_time {

let n = rand::thread_rng().gen_range(0, nn) + 1;

let mut cuts = random_array(n, cut_v);

let mut posions = random_array(n, posion_v);

let hp = rand::thread_rng().gen_range(0, hp_v) + 1;

let ans1 = fast1(&mut cuts, &mut posions, hp);

let ans2 = fast2(&mut cuts, &mut posions, hp);

if ans1 != ans2 {

println!("cuts = {:?}", cuts);

println!("posions = {:?}", posions);

println!("i = {:?}", i);

println!("ans1 = {:?}", ans1);

println!("ans2 = {:?}", ans2);

println!("出错了!");

break;

}

}

println!("测试结束");

}

// 不算好的方法

// 为了验证

fn fast1(cuts: &mut Vec, poisons: &mut Vec, hp: i32) -> i32 {

let mut sum = 0;

for num in poisons.iter() {

sum += *num;

}

let mut dp: Vec>> = repeat(

repeat(repeat(0).take((sum + 1) as usize).collect())

.take((hp + 1) as usize)

.collect(),

)

.take(cuts.len())

.collect();

return process1(cuts, poisons, 0, hp, 0, &mut dp);

}

fn process1(

cuts: &mut Vec,

poisons: &mut Vec,

index: i32,

mut rest_hp: i32,

poison_effect: i32,

dp: &mut Vec>>,

) -> i32 {

rest_hp -= poison_effect;

if rest_hp <= 0 {

return index + 1;

}

// restHp > 0

if index == cuts.len() as i32 {

if poison_effect == 0 {

return i32::MAX;

} else {

return cuts.len() as i32 + 1 + (rest_hp + poison_effect - 1) / poison_effect;

}

}

if dp[index as usize][rest_hp as usize][poison_effect as usize] != 0 {

return dp[index as usize][rest_hp as usize][poison_effect as usize];

}

let p1 = if rest_hp <= cuts[index as usize] {

index + 1

} else {

process1(

cuts,

poisons,

index + 1,

rest_hp - cuts[index as usize],

poison_effect,

dp,

)

};

let p2 = process1(

cuts,

poisons,

index + 1,

rest_hp,

poison_effect + poisons[index as usize],

dp,

);

let ans = get_min(p1, p2);

dp[index as usize][rest_hp as usize][poison_effect as usize] = ans;

return ans;

}

fn get_min(a: T, b: T) -> T {

if a < b {

a

} else {

b

}

}

fn get_max(a: T, b: T) -> T {

if a > b {

a

} else {

b

}

}

// 真正想实现的方法

// O(N * log(hp))

fn fast2(cuts: &mut Vec, poisons: &mut Vec, hp: i32) -> i32 {

// 怪兽可能的最快死亡回合

let mut l = 1;

// 怪兽可能的最晚死亡回合

let mut r = hp + 1;

let mut m: i32;

let mut ans = i32::MAX;

while l <= r {

m = l + ((r - l) >> 1);

if ok(cuts, poisons, hp as i64, m) {

ans = m;

r = m - 1;

} else {

l = m + 1;

}

}

return ans;

}

fn ok(cuts: &mut Vec, posions: &mut Vec, mut hp: i64, limit: i32) -> bool {

let n = get_min(cuts.len() as i32, limit);

let mut i = 0;

let mut j = 1;

while i < n {

hp -= get_max(

cuts[i as usize] as i64,

(limit - j) as i64 * posions[i as usize] as i64,

);

if hp <= 0 {

return true;

}

i += 1;

j += 1;

}

return false;

}

// 为了测试

fn random_array(n: i32, v: i32) -> Vec {

let mut ans: Vec = vec![];

for _ in 0..n {

ans.push(rand::thread_rng().gen_range(0, v) + 1);

}

return ans;

}

执行结果如下：

左神java代码

相关链接

 您阅读本篇文章共花了：