2023-04-05：做甜点需要购买配料，目前共有n种基料和m种配料可供选购。
制作甜点需要遵循以下几条规则：
必须选择1种基料；可以添加0种、1种或多种配料，每种类型的配料最多添加2份，
给定长度为n的数组base, base[i]表示第i种基料的价格，
给定长度为m的数组topping, topping[j]表示第j种配料的价格，
给定一个正数target，表示你做的甜点最终的价格要尽量接近这个数值。
返回最接近这个数值的价格是多少。
如果有多个方案，都最接近target，返回价格最小的那个答案。
1 <= n,m <= 10，
1 <= base[i], topping[j] <= 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)+n*logm))。

空间复杂度：

由于需要存储所有辅料组合方式所能产生的价格，因此需要用到一个静态数组来存储这些价格，其空间复杂度为 O(3^m)。
因此，该算法的空间复杂度为 O(3^m)。

测试

最后，为了验证代码实现的正确性，进行了功能测试和性能测试。在功能测试中，随机生成了多组数据对两种算法进行了比较，并检验它们的输出结果是否一致。在性能测试中，随机生成了一个较大的数据集，对两种算法的运行时间进行了比较。

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!("性能测试结束");
}

本作品采用《CC 协议》，转载必须注明作者和本文链接