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
}
执行结果如下：
京公网安备 11010502036488号