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<i32>, poisons: &mut Vec<i32>, hp: i32) -> i32 {
let mut sum = 0;
for num in poisons.iter() {
sum += *num;
}
let mut dp: Vec<Vec<Vec<i32>>> = 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<i32>,
poisons: &mut Vec<i32>,
index: i32,
mut rest_hp: i32,
poison_effect: i32,
dp: &mut Vec<Vec<Vec<i32>>>,
) -> 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<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
// 真正想实现的方法
// O(N * log(hp))
fn fast2(cuts: &mut Vec<i32>, poisons: &mut Vec<i32>, 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<i32>, posions: &mut Vec<i32>, 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<i32> {
let mut ans: Vec<i32> = vec![];
for _ in 0..n {
ans.push(rand::thread_rng().gen_range(0, v) + 1);
}
return ans;
}
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_08_3_week/Code02_CutOrPoison.java)