2022-12-14：给定一个正数n, 表示从0位置到n-1位置每个位置放着1件衣服 从0位置到n-1位置不仅有衣服，每个位置还摆着1个机器人 给定两个长度为n的数组，powers和rates pow

2022-12-14：给定一个正数n, 表示从0位置到n-1位置每个位置放着1件衣服
从0位置到n-1位置不仅有衣服，每个位置还摆着1个机器人
给定两个长度为n的数组，powers和rates
powers[i]表示i位置的机器人的启动电量
rates[i]表示i位置的机器人收起1件衣服的时间
使用每个机器人只需要付出启动电量
当i位置的机器人收起i位置的衣服，它会继续尝试往右收起i+1位置衣服
如果i+1位置的衣服已经被其他机器人收了或者其他机器人正在收
这个机器人就会停机, 不再收衣服。
不过如果它不停机，它会同样以rates[i]的时间来收起这件i+1位置的衣服
也就是收衣服的时间为每个机器人的固定属性，当它收起i+1位置的衣服，
它会继续检查i+2位置…一直到它停机或者右边没有衣服可以收了
形象的来说，机器人会一直尝试往右边收衣服，收k件的话就耗费k * rates[i]的时间
但是当它遇见其他机器人工作的痕迹，就会认为后面的事情它不用管了，进入停机状态
你手里总共有电量b，准备在0时刻将所有想启动的机器人全部一起启动
过后不再启动新的机器人，并且启动机器人的电量之和不能大于b
返回在最佳选择下，假快多久能收完所有衣服
如果无论如何都收不完所有衣服，返回-1
给定数据: int n, int b, int[] powers, int[] rates
数据范围:
powers长度 == rates长度 == n <= 1000
1 <= b <= 10^5
1 <= powers[i]、rates[i] <= 10^5
0号 : 10^5 * 10^3 -> 10^8
log 10^8 * N^2 -> 27 * 10^6 -> 10^7
优化之后 : (log10^8) -> 27 * 1000 * 10
来自美团。

答案2022-12-14：

二分答案法+线段树优化枚举。
时间复杂度O(N * logN * log(rates[0] * N))。

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

use rand::Rng;

use std::iter::repeat;

fn main() {

    let nn: i32 = 200;

    let bb: i32 = 100;

    let pp: i32 = 20;

    let rr: i32 = 20;

    let test_time: i32 = 100;

    println!("测试开始");

    for i in 0..test_time {

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

        let b: i32 = rand::thread_rng().gen_range(0, bb) + 1;

        let mut powers = random_array(n, pp);

        let mut rates = random_array(n, rr);

        let ans1 = fast1(n, b, &mut powers, &mut rates);

        let ans2 = fast2(n, b, &mut powers, &mut rates);

        let ans3 = fast3(n, b, &mut powers, &mut rates);

        if ans1 != ans2 || ans1 != ans3 {

            println!("出错了!");

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

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

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

            println!("ans3 = {}", ans3);

            break;

        }

    }

    println!("测试结束");

}

// 通过不了的简单动态规划方法

// 只是为了对数器验证

fn fast1(n: i32, b: i32, powers: &mut Vec<i32>, rates: &mut Vec<i32>) -> i32 {

    // int[][] dp = new int[n][b + 1];

    // for (int i = 0; i < n; i++) {

    // 	for (int j = 0; j <= b; j++) {

    // 		dp[i][j] = -1;

    // 	}

    // }

    let mut dp: Vec<Vec<i32>> = repeat(repeat(-1).take((b + 1) as usize).collect())

        .take(n as usize)

        .collect();

    let ans = process1(powers, rates, n, 0, b, &mut dp);

    return if ans == i32::MAX { -1 } else { ans };

}

// i....这些衣服

// 由i....这些机器人负责

// 在剩余电量还有rest的情况下

// 收完i....这些衣服最少时间是多少

// 如果怎么都收不完

// 返回Integer.MAX_VALUE

fn process1(

    powers: &mut Vec<i32>,

    rates: &mut Vec<i32>,

    n: i32,

    i: i32,

    rest: i32,

    dp: &mut Vec<Vec<i32>>,

) -> i32 {

    if i == n {

        return 0;

    }

    if powers[i as usize] > rest {

        return i32::MAX;

    }

    if dp[i as usize][rest as usize] != -1 {

        return dp[i as usize][rest as usize];

    }

    let mut ans = i32::MAX;

    for j in i..n {

        let cur_cost = (j - i + 1) * rates[i as usize];

        let next_cost = process1(powers, rates, n, j + 1, rest - powers[i as usize], dp);

        let cur_ans = get_max(cur_cost, next_cost);

        ans = get_min(ans, cur_ans);

    }

    dp[i as usize][rest as usize] = ans;

    return ans;

}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {

    if a > b {

        a

    } else {

        b

    }

}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {

    if a < b {

        a

    } else {

        b

    }

}

// 正式方法

// 时间复杂度O( N^2 * log(rates[0] * n))

// 揭示了大的思路，可以继续用线段树优化枚举，详情看fast3

// 解题思路:

// 二分答案

// 定义函数minPower：

// 如果一定要在time时间内捡完所有衣服，请返回使用最少的电量

// 如果minPower，这个函数能实现

// 那么只要二分出最小的答案即可

fn fast2(n: i32, b: i32, powers: &mut Vec<i32>, rates: &mut Vec<i32>) -> i32 {

    if n == 0 {

        return 0;

    }

    if b == 0 || powers[0] > b {

        return -1;

    }

    // 最小时间只可能在[1, rates[0] * n]范围上

    let mut l = 1;

    let mut r = rates[0] * n;

    let mut m = 0;

    let mut ans = -1;

    // 二分答案

    // 规定的时间就是m

    // minPower(powers, rates, m):

    // 如果一定要在time时间内捡完所有衣服，返回最小电量

    // 如果这个最小电量 <= 总电量，说明m时间可行，左侧继续二分答案

    // 如果这个最小电量 > 总电量，说明m时间不可行，右侧继续二分答案

    while l <= r {

        m = (l + r) / 2;

        if min_power2(powers, rates, m) <= b {

            ans = m;

            r = m - 1;

        } else {

            l = m + 1;

        }

    }

    return ans;

}

// 给定所有机器人的启动电量 powers[]

// 给定所有机器人的收一件衣服的时间 rates[]

// 一定要在time时间内，收完所有衣服！

// 返回 : 至少需要的电量!

fn min_power2(powers: &mut Vec<i32>, rates: &mut Vec<i32>, time: i32) -> i32 {

    let mut dp: Vec<i32> = repeat(-1).take(powers.len()).collect();

    return process2(powers, rates, 0, time, &mut dp);

}

// i....这么多的衣服

// 在time时间内一定要收完

// 返回最小电量

// 如果怎么都收不完，返回系统最大值

// N^2

fn process2(

    powers: &mut Vec<i32>,

    rates: &mut Vec<i32>,

    i: i32,

    time: i32,

    dp: &mut Vec<i32>,

) -> i32 {

    let n = powers.len() as i32;

    if i == n {

        return 0;

    }

    if dp[i as usize] != -1 {

        return dp[i as usize];

    }

    // i.....

    // 收当前i位置这一件衣服的时间

    let mut used_time = rates[i as usize];

    let mut next_min_power = i32::MAX;

    let mut j = i;

    while j < n && used_time <= time {

        // i...i i+1....

        // i......i+1 i+2...

        // i...........i+2 i+3...

        // i....j j+1....

        next_min_power = get_min(next_min_power, process2(powers, rates, j + 1, time, dp));

        used_time += rates[i as usize];

        j += 1;

    }

    let mut ans = if next_min_power == i32::MAX {

        next_min_power

    } else {

        (powers[i as usize] + next_min_power)

    };

    dp[i as usize] = ans;

    return ans;

}

// fast2的思路 + 线段树优化枚举

// 时间复杂度O(N * logN * log(rates[0] * N))

fn fast3(n: i32, b: i32, powers: &mut Vec<i32>, rates: &mut Vec<i32>) -> i32 {

    if (n == 0) {

        return 0;

    }

    if (b == 0 || powers[0] > b) {

        return -1;

    }

    let mut l = 1;

    let mut r = rates[0] * n;

    let mut m = 0;

    let mut ans = -1;

    while l <= r {

        m = (l + r) / 2;

        if min_power3(powers, rates, m) <= b {

            ans = m;

            r = m - 1;

        } else {

            l = m + 1;

        }

    }

    return ans;

}

fn min_power3(powers: &mut Vec<i32>, rates: &mut Vec<i32>, time: i32) -> i32 {

    let n = powers.len() as i32;

    let mut dp: Vec<i32> = repeat(0).take((n + 1) as usize).collect();

    //      dp[n-1]  dp[n]

    //         n-1     n

    let mut st = SegmentTree::new(n + 1);

    st.update(n, 0);

    let mut i = n - 1;

    while i >= 0 {

        if rates[i as usize] > time {

            dp[i as usize] = i32::MAX;

        } else {

            let j = get_min(i + (time / rates[i as usize]) - 1, n - 1);

            // for.... logN

            let next = st.min(i + 1, j + 1);

            let ans = if next == i32::MAX {

                next

            } else {

                (powers[i as usize] + next)

            };

            dp[i as usize] = ans;

        }

        st.update(i, dp[i as usize]);

        i -= 1;

    }

    return dp[0];

}

struct SegmentTree {

    n: i32,

    min: Vec<i32>,

}

impl SegmentTree {

    fn new(size: i32) -> Self {

        let n = size;

        let min: Vec<i32> = repeat(i32::MIN).take((n << 2) as usize).collect();

        Self { n, min }

    }

    fn min(&mut self, mut l: i32, mut r: i32) -> i32 {

        return self.min0(l + 1, r + 1, 1, self.n, 1);

    }

    fn update(&mut self, mut i: i32, v: i32) {

        self.update0(i + 1, i + 1, v, 1, self.n, 1);

    }

    fn push_up(&mut self, rt: i32) {

        self.min[rt as usize] = get_min(

            self.min[(rt << 1) as usize],

            self.min[(rt << 1 | 1) as usize],

        );

    }

    fn update0(&mut self, ll: i32, rr: i32, cc: i32, l: i32, r: i32, rt: i32) {

        if ll <= l && r <= rr {

            self.min[rt as usize] = cc;

            return;

        }

        let mid = (l + r) >> 1;

        if ll <= mid {

            self.update0(ll, rr, cc, l, mid, rt << 1);

        }

        if rr > mid {

            self.update0(ll, rr, cc, mid + 1, r, rt << 1 | 1);

        }

        self.push_up(rt);

    }

    fn min0(&mut self, ll: i32, rr: i32, l: i32, r: i32, rt: i32) -> i32 {

        if ll <= l && r <= rr {

            return self.min[rt as usize];

        }

        let mid = (l + r) >> 1;

        let mut left = i32::MAX;

        let mut right = i32::MAX;

        if ll <= mid {

            left = self.min0(ll, rr, l, mid, rt << 1);

        }

        if rr > mid {

            right = self.min0(ll, rr, mid + 1, r, rt << 1 | 1);

        }

        return get_min(left, right);

    }

}

// 为了测试

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

    let mut ans = vec![];

    for i in 0..n {

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

    }

    ans

}

执行结果如下：

左神java代码

2022-12-14：给定一个正数n, 表示从0位置到n-1位置每个位置放着1件衣服 从0位置到n-1位置不仅有衣服，每个位置还摆着1个机器人 给定两个长度为n的数组，powers和rates pow的相关教程结束。