meet in the middle

约 144 个字

暴力搜索是 $O(2^n)$，折半搜索是 $O(2^{n/2})$ + 合并的复杂度

搜索过程分成两半，再合并两半结果

例题1

搜索出前半部分的比赛的组合票价，后半部分的比赛的组合票价

然后两个结果都排序，双指针合并结果

例题2

搜索出前半数的组合和，后半数的组合和

然后两个结果都排序

因为 $x,y<m$，所以 $x+y<2m$

对于 $x+y>m$ 的，取最大 $x+y$ 为一种可能方案

对于 $x+y<m$ 的，双指针处理可能方案