#14: 解題思路


911091@stu.cchs.chc.edu.tw (17莊明達 David)

學校 : 彰化縣精誠中學
編號 : 4
來源 : [111.246.30.44]
最後登入時間 :
2023-06-10 18:41:31
a161. Q-2-10. 子集合的和(折半枚舉) -- AP325 | From: [125.231.104.12] | 發表日期 : 2022-02-05 20:46

直接做複雜度 O(2n),帶入限制 2^38 ≈ 1e11 直接 TLE 💥

先把陣列切成左半右半分別枚舉,複雜度 O(2n/2),弄出兩堆數組 S1、S2,剩下橫跨陣列左右半的組合沒有被枚舉到,也就是 S1、S2 各挑一個數字出來的和 (陣列左半某組合 + 陣列右半某組合 = 陣列橫跨左右半的某組合)

也就是說,對於 S1 的每個數字 a,你想要找到 S2 裡的一個數字 b 使 a+b 為最大,又不超過 P。

先將 S1、S2 排序,再利用二分搜就能夠很快達到這樣的目的。 複雜度 O( 2n/2(枚舉 S1、S2) + 2n/2log2n/2(排序) + 2n/2log2n/2(對S1所有元素在S2裡二分搜)) = O(2n/2log2n/2

 
ZeroJudge Forum