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;}
评论