2023-04-05：做甜点需要购买配料，目前共有n种基料和m种配料可供选购。
制作甜点需要遵循以下几条规则：
必须选择1种基料；可以添加0种、1种或多种配料，每种类型的配料最多添加2份，
给定长度为n的数组base, basei表示第i种基料的价格，
给定长度为m的数组topping, toppingj表示第j种配料的价格，
给定一个正数target，表示你做的甜点最终的价格要尽量接近这个数值。
返回最接近这个数值的价格是多少。
如果有多个方案，都最接近target，返回价格最小的那个答案。
1 <= n,m <= 10，
1 <= basei, toppingj <= 10 ^ 4，
1 <= target <= 10 ^ 4。
来自华为。
答案2023-04-05：
方法1：有序表
1.首先创建一个空的有序表 set。
2.然后使用递归方式枚举所有辅料的组合方式，并将每种组合方式所能产生的价格放入有序表里。
3.接着遍历主料的价格数组，对于每个价格，从有序表中找到其中最接近且小于等于 target - num 的价格 floor 和最接近且大于等于 target - num 的价格 ceiling，然后计算出与主料价格相加最接近目标价格 target 的套餐价格 cur，分别跟当前的最优解 ans 比较，选取更优的一种。
4.对于每种辅料的组合方式和每个主料的价格，都要进行以上操作来更新最优解。
时间复杂度：
对于辅料的组合方式，每个辅料有三种选择（选或不选、加一份或两份），因此总共有 3^m 种组合方式。
对于主料的价格，需要在有序表中查找最接近且小于等于 target - num 的价格和最接近且大于等于 target - num 的价格。由于使用了红黑树实现的有序表，所以平均查找复杂度为 O(logn)，其中 n <= 3^m 是有序表中元素的个数。
因此，该算法的时间复杂度为 O(n log n m 3 ^ m log (3^m))。
空间复杂度：
由于需要存储所有辅料组合方式所能产生的价格，因此需要用到一个 BTreeSet 来存储这些价格，其空间复杂度为 O(m 3^m)。
因此，该算法的空间复杂度为 O(m 3^m)。
方法2：数组排序 二分
1.首先创建一个静态数组 COLLECT 和一个静态变量 SIZE。
2.然后使用递归方式枚举所有辅料的组合方式，并将每种组合方式所能产生的价格存入 COLLECT 数组中，并更新 SIZE 的值。
3.接着将 COLLECT 数组中存储的所有价格以非降序排列。
4.对于每个主料的价格，从 COLLECT 数组中找到其中最接近且小于等于 target - num 的价格 floor 和最接近且大于等于 target - num 的价格 ceiling，然后计算出与主料价格相加最接近目标价格 target 的套餐价格 cur，分别跟当前的最优解 ans 比较，选取更优的一种。
5.对于每种辅料的组合方式和每个主料的价格，都要进行以上操作来更新最优解。
6.注意，在二分查找 COLLECT 数组时需要使用 unsafe 代码块，因为 Rust 的 borrow checker 无法保证并发访问 COLLECT 数组的安全性。
时间复杂度：
对于辅料的组合方式，每个辅料有三种选择（选或不选、加一份或两份），因此总共有 3^m 种组合方式。
先对数组进行组合生成和排序，其中生成的元素个数是 3 ^ m，而排序的时间复杂度为 O(3 ^ m *log 3^m)。
对于主料的价格，需要在排序后的数组中进行二分查找。由于数组是有序的，因此每次查找的时间复杂度为 O(log 3^m) =O(m)。
因此，该算法的时间复杂度为 O(m(3^mlog(3 ^ m) nlogm))。
空间复杂度：
由于需要存储所有辅料组合方式所能产生的价格，因此需要用到一个静态数组来存储这些价格，其空间复杂度为 O(3^m)。
因此，该算法的空间复杂度为 O(3^m)。
测试
最后，为了验证代码实现的正确性，进行了功能测试和性能测试。在功能测试中，随机生成了多组数据对两种算法进行了比较，并检验它们的输出结果是否一致。在性能测试中，随机生成了一个较大的数据集，对两种算法的运行时间进行了比较。
rust完整代码如下：
代码语言：rust复制use std::cmp::Ordering;
use std::collections::BTreeSet;
// 方法1，用有序表的方法
fn closed_target1(base: &[i32], topping: &[i32], target: i32) -> i32 {
// 辅料所能产生的所有价格！
// 0 5 15 23
let mut set = BTreeSet::new();
// 暴力展开！收集所有能产生的价格！放入辅料表里去！
process1(topping, 0, 0, &mut set);
let mut ans = i32::MAX;
for &num in base.iter() {
// 枚举每一种主料的价格！
// 最终能搭配出来的最接近的价格
let mut cur = num;
// 20 100
// 110 100
if num < target {
// cur < 要求
// 60 100
// 40
let rest = target - num;
// <= rest 最接近的！
let floor = set.range(..=rest).next_back();
// >= rest 最接近的！
let ceiling = set.range(rest..).next();
cur = match (floor, ceiling) {
(Some(f), Some(c)) => {
if rest - f <= c - rest {
*f
} else {
*c
}
}
(Some(f), None) => *f,
(None, Some(c)) => *c,
(None, None) => 0, // 处理边界情况
};
// cur会选择floor,或ceiling，谁加上最接近target选谁！
}
if (cur - target).abs() < (ans - target).abs()
|| (cur - target).abs() == (ans - target).abs() && cur < ans
{
ans = cur;
}
}
ans
}
// 暴力展开！收集所有能产生的价格！放入辅料表里去！
// topping[index....]
// topping[0...index-1] sum
fn process1(topping: &[i32], index: usize, sum: i32, set: &mut BTreeSet<i32>) {
if index == topping.len() {
set.insert(sum);
} else {
process1(topping, index 1, sum, set);
process1(topping, index 1, sum topping[index], set);
process1(topping, index 1, sum (topping[index] << 1), set);
}
}
// 方法2，用数组排序 二分的方法
static mut COLLECT: [i32; 14348907] = [0; 14348907];
static mut SIZE: usize = 0;
fn closed_target2(base: &[i32], topping: &[i32], target: i32) -> i32 {
unsafe {
SIZE = 0;
process2(topping, 0, 0);
let size = SIZE;
COLLECT[..size].sort_unstable();
let mut ans = i32::MAX;
for &num in base.iter() {
let mut cur = num;
if num < target {
let rest = target - num;
let floor = floor(rest);
let ceiling = ceiling(rest);
if floor == None || ceiling == None {
cur = if floor == None {
ceiling.unwrap()
} else {
floor.unwrap()
};
} else {
cur = if rest - floor.unwrap() <= ceiling.unwrap() - rest {
floor.unwrap()
} else {
ceiling.unwrap()
};
}
}
if (cur - target).abs() < (ans - target).abs()
|| (cur - target).abs() == (ans - target).abs() && cur < ans
{
ans = cur;
}
}
ans
}
}
fn process2(topping: &[i32], index: usize, sum: i32) {
unsafe {
if index == topping.len() {
COLLECT[SIZE] = sum;
SIZE = 1;
} else {
process2(topping, index 1, sum);
process2(topping, index 1, sum topping[index]);
process2(topping, index 1, sum (topping[index] << 1));
}
}
}
fn floor(num: i32) -> Option<i32> {
unsafe {
let mut l = 0;
let mut r = SIZE - 1;
let mut ans = None;
while l <= r {
let m = (l r) / 2;
match COLLECT[m].cmp(&num) {
Ordering::Less => {
ans = Some(COLLECT[m]);
l = m 1;
}
Ordering::Greater => r = m - 1,
Ordering::Equal => {
ans = Some(COLLECT[m]);
break;
}
}
}
ans
}
}
fn ceiling(num: i32) -> Option<i32> {
unsafe {
let mut l = 0;
let mut r = SIZE - 1;
let mut ans = None;
while l <= r {
let m = (l r) / 2;
match COLLECT[m].cmp(&num) {
Ordering::Less => l = m 1,
Ordering::Greater => {
ans = Some(COLLECT[m]);
r = m - 1;
}
Ordering::Equal => {
ans = Some(COLLECT[m]);
break;
}
}
}
ans
}
}
// 为了验证
fn random_array(n: usize, v: i32) -> Vec<i32> {
let mut arr = vec![0; n];
for i in 0..n {
arr[i] = (rand::random::<i32>() % v).abs() 1;
}
arr
}
// 为了验证
fn main() {
let N: usize = 8;
let V: i32 = 10000;
let test_time = 5000;
println!("功能测试开始");
for _ in 0..test_time {
let n = (rand::random::<usize>() % N) 1;
let m = (rand::random::<usize>() % N) 1;
let base = random_array(n, V);
let topping = random_array(m, V);
let target = (rand::random::<i32>() % V).abs() 1;
let ans1 = closed_target1(&base, &topping, target);
let ans2 = closed_target2(&base, &topping, target);
assert_eq!(ans1, ans2);
}
println!("功能测试结束");
println!("性能测试开始");
let N: usize = 15;
let V: i32 = 10000;
let base = random_array(N, V);
let topping = random_array(N, V);
let target = (rand::random::<i32>() % V).abs() 1;
println!("base数组长度 : {}", N);
println!("topping数组长度 : {}", N);
println!("数值范围 : {}", V);
let start = std::time::Instant::now();
closed_target2(&base, &topping, target);
let duration = start.elapsed();
println!("运行时间 : {} 毫秒", duration.as_millis());
println!("性能测试结束");
}
