直接做複雜度 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)