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

題目理解後就變普通的終極密碼了

大師捏