解题思路
本题是带基数约束的划分:把偶数个工单均分成两班,最小化两班收益差。值班侧先选高收益班次,差值为 ∣2S−V∣,与谁拿走哪一班无关,于是只需在「恰好 2n 个工单」的子集中,让子集和 S 尽量接近总和的一半。
- n≤30,直接枚举 C(n,n/2) 过大,采用折半枚举。
- 把数组切成左右两半,各约 2n 个。对每一半枚举所有子集,按所选个数把子集和存进列表并排序。
- 左半选 k 个、右半选 2n−k 个,在两列有序和上二分,使两部分和尽量接近 ⌊V/2⌋。
- 所有 k 取最小 ∣V−2S∣ 即为答案。