Re: [閒聊] 每日leetcode
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
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1749801714.A.02E.html
→
06/13 16:03,
5月前
, 1F
06/13 16:03, 1F
→
06/13 16:07,
5月前
, 2F
06/13 16:07, 2F
→
06/13 16:21,
5月前
, 3F
06/13 16:21, 3F
討論串 (同標題文章)
完整討論串 (本文為第 1446 之 1548 篇)：