2616. Minimize the Maximum Difference of Pairs
https://leetcode.com/problems/minimize-the-maximum-difference-of-pairs/
题目：
阿巴阿巴 题意写得有点姆咪
我让AI整理的
1. 阵列中可以挑“p 组 pair（不能重复 index）”
2. 每组 pair 计算“相减的绝对值差”
3. 目标是“让这 p 组 pair 中，最大的一组差距（max(diff)） 最小化”
4. 换句话说 → 找一个最小可能的 X，让“能配出 p 组 pair，且每组差距 X”
思路：
先排序 从 index = 1 开始走
然后二分搜寻 起始猜 (最大+最小)/2
满足就 high = guest 往下缩圈
不满足就 low = guest + 1 往上缩圈
每次比较前面减后面能不能满足条件
条件超过 p 就可先跳
不然效能贼差 只能打败 10%
Code:
impl Solution {
pub fn minimize_max(nums: Vec<i32>, p: i32) -> i32 {
let mut nums = nums;
nums.sort();
let mut low = 0;
let mut high = nums[nums.len() - 1] - nums[0];
while low < high {
let guest = (high + low) / 2;
if Self::can_get_p_pairs(&nums, p, guest) {
high = guest;
} else {
low = guest + 1;
}
}
low
}
pub fn can_get_p_pairs(nums: &Vec<i32>, p: i32, guest: i32) -> bool {
let mut pair_count = 0;
let mut index = 1;
while index < nums.len() {
if nums[index] - nums[index - 1] <= guest {
pair_count += 1;
if pair_count >= p {
return true;
}
index += 2;
} else {
index += 1;
}
}
pair_count >= p
}
}

宝 为啥摸想那么快 :OO

题目理解后就变普通的终极密码了

大师捏