2022-11-09：给定怪兽的血量为hp 第i回合如果用刀砍，怪兽在这回合会直接掉血，没有后续效果第i回合

moonfdd 的个人博客 / 32 / 0 / 创建于 1年前

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