2023-04-08：小红有n个朋友, 她准备开个宴会，邀请一些朋友， i号朋友的愉悦值为a[i]，财富值为b[i]， 如果两个朋友同时参加宴会，这两个朋友之间的隔阂是其财富值差值的绝对值， 宴会的隔阂值，是财富差距最大的两人产生的财富值差值的绝对值， 宴会的愉悦值，是所有参加宴会朋友的愉悦值总和。 小红可以邀请任何人， 希望宴会的愉悦值不能小于k的情况下， 宴会的隔阂值能最小是多少？ 如果做不到，返回-1。 1 <= n <= 2 * 10^5， 1 <= 愉悦值、财富值 <= 10^9， 1 <= k <= 10^14。 来自蚂蚁金服。
答案2023-04-08：
方法一：暴力枚举
思路：
对于每一个可能的区间，计算区间中 bb 数组元素的最大值和最小值，然后计算跨度并统计愉悦值。记录跨度最小的区间的元素和与跨度，最后返回跨度最小的值。
步骤：
1.使用递归函数枚举所有可能的区间，函数参数包括数组 a、数组 b、当前递归到的位置 i、剩余需要选择的元素个数 restr，以及已经选过的区间中的最小值 min 和最大值 max。 2.当需要选择的元素个数 rest 小于等于 0 时，返回跨度最小的区间对应数组 b 的元素的最大值和最小值之差； 3.当递归到数组 a 的末尾时，返回一个足够大的数（这里使用了 Rust 中整型类型 i32 的最大值）表示无法选出符合要求的区间； 4.否则，分别计算选择当前位置的元素和不选择当前位置的元素两种情况下所能得到的跨度最小的区间，然后取两者的最小值作为函数的返回值。
时间复杂度：O(2^n)，其中 n 是数组长度。
空间复杂度：O(n)。
方法二：二分答案
思路：
对于每一个可能的区间跨度 x，我们可以判断是否有一个区间的元素和最接近 k 且其跨度不大于 x。具体实现时，先将数组 b 按照元素大小排序，然后利用二分查找的思想，在排序后的数组上二分答案。
步骤：
1.将数组 b 按照元素大小排序，并记录 b 数组的最小值和最大值； 2.使用二分答案法，在区间 [0,max−min] 上进行二分，其中 max 和 min 分别为 b 数组中的最大值和最小值； 3.对于每一个二分得到的可能的跨度 x，计算在跨度不大于 x 的情况下，宴会的愉悦值能否大于等于 k。具体实现时，使用双指针法维护当前区间的左右端点，计算当前区间内 a 数组元素的和并记录其最大值； 4.如果在跨度不大于 x 的情况下宴会的愉悦值大于等于 k，则更新答案，并将区间左端点右移； 5.否则，将区间右端点右移。
时间复杂度：O(nlognlogV)，其中 n 是数组长度，V 是数组元素的最大值。
空间复杂度：O(n)。
方法三：滑动窗口
思路：
我们可以使用双指针法在 b 数组上维护一个区间，使得该区间的财富值差距不大于当前尝试的跨度，并计算在该区间中元素值和能否大于等于 k。具体实现时，先将数组 b 按照元素大小排序，然后使用两个指针 l 和 r 维护当前区间，用变量 happy 记录当前区间内元素值之和，每次将指针向右移动时对 happy 进行更新，直到找到一个满足愉悦值大于等于 k 的区间。
步骤：
1.将数组 b 按照元素大小排序； 2.使用双指针法，在数组 b 上维护一个区间，使得该区间的财富值差距不大于当前尝试的跨度，并计算在该区间中元素值和能否大于等于 k。具体实现时，使用两个指针 l 和 rr 维护当前区间，用变量 happy 记录当前区间内元素值之和。每次将指针向右移动时对 happy 进行更新，并在 happy≥k 的情况下更新答案； 3.如果找到了一个满足愉悦值大于等于 k 的区间，则返回该区间的跨度；否则返回 −1。
时间复杂度：O(nlogn)，其中 n 是数组长度。
空间复杂度：O(n)。
三种方法分析
从时间复杂度和空间复杂度两个方面来看，方法二和方法三都比方法一要好得多。在实际应用中，我们应该优先选择方法二或方法三。
rust完整代码如下：
fn less_gap1(a: &Vec
let ans = process(a, b, 0, k, std::i32::MAX, std::i32::MIN);
return if ans < std::i32::MAX as i64 {
ans as i32
} else {
-1
};
}
fn process(a: &Vec
if rest <= 0 {
(max - min).abs() as i64
} else if i == a.len() {
std::i32::MAX as i64
} else {
let p1 = process(a, b, i + 1, rest, min, max);
let p2 = process(a, b, i + 1, rest - a[i], min.min(b[i]), max.max(b[i]));
p1.min(p2)
}
}
fn less_gap2(a: &Vec
let n = a.len();
let mut f = vec![vec![0; 2]; n];
let mut min = b[0];
let mut max = b[0];
for i in 0..n {
f[i][0] = a[i];
f[i][1] = b[i];
min = min.min(b[i]);
max = max.max(b[i]);
}
f.sort_by_key(|x| x[1]);
let (mut l, mut r) = (0, max - min);
let mut ans = -1;
while l <= r {
let m = (l + r) / 2;
if max_happy(&f, m) >= k {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
fn max_happy(f: &Vec
let n = f.len();
let mut sum = 0;
let mut ans = 0;
let mut r = 0;
for l in 0..n {
while r < n && f[r][1] - f[l][1] <= limit {
sum += f[r][0];
r += 1;
}
ans = ans.max(sum);
sum -= f[l][0];
r = r.max(l + 1);
}
return ans as i64;
}
fn less_gap3(a: &Vec
let n = a.len();
let mut f = vec![vec![0; 2]; n];
for i in 0..n {
f[i][0] = a[i];
f[i][1] = b[i];
}
f.sort_by_key(|x| x[1]);
let (mut ans, mut happy) = (std::i32::MAX, 0_i64);
let (mut l, mut r) = (0, 0);
while l < n {
while r < n && happy < k {
happy += f[r][0] as i64;
r += 1;
}
if happy >= k {
ans = ans.min(f[r - 1][1] - f[l][1]);
}
happy -= f[l][0] as i64;
l += 1;
}
return if ans == std::i32::MAX { -1 } else { ans };
}
fn random_array(n: usize, v: i32) -> Vec
let mut arr = vec![0; n];
for i in 0..n {
arr[i] = (rand::random::
}
return arr;
}
fn main() {
const N: usize = 15;
const V: i32 = 20;
const TEST_TIME: i32 = 5000;
println!("功能测试开始");
for _ in 0..TEST_TIME {
let n = rand::random::
let a = random_array(n, V);
let b = random_array(n, V);
let k = rand::random::
let ans1 = less_gap1(&a, &b, k as i32);
let ans2 = less_gap2(&a, &b, k as i64);
let ans3 = less_gap3(&a, &b, k as i64);
if ans1 != ans2 || ans1 != ans3 {
println!("出错了!");
println!("a = {:?}", a);
println!("b = {:?}", b);
println!("k = {}", k);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
println!("ans3 = {}", ans3);
return;
}
}
println!("功能测试结束");
}
精彩链接
您阅读本篇文章共花了：
发表评论