题意
给出 \(n\) 个数 \(a_i\)，你需要把这些数分成三组，使得每组之和的极差最小，给出方案。
\(3\le n\le 25,1\le a_i\le 10^7\)。
思路
\(n\le 25\)，考虑折半搜索。
发现 \(3^{13}\approx 10^6\)，所以复杂度是对的。
于是问题就变为给出两个三元组集合 \((a_i,b_i,c_i),(a'_j,b'_j,c'_j)\)，要求从两组集合中分别选出一个三元组使得 \((a_i+a'_j,b_i+b'_j,c_i+c'_j)\) 的极差最小。
容易发现只需要统计所有 \(a_i+a'_j\ge b_i+b'_j\ge c_i+c'_j\) 的集合，此时的极差为 \(a_i-c_i+a'_j-c'_j\)。
令 \(x_i=a_i-b_i,y_i=b_i-c_i,x'_j=a'_j-b'_j,y'_j=b'_j-c'_j\)，题目转换为给出两个二元组集合 \((x_i,y_i),(x'_j,y'_j)\)，从两组集合中分别选出一个二元组满足 \(x_i\ge -x'_j,y_i\ge -y'_j\)，且 \((x_i+y_i+x'_j+y'_j)\) 最小。
剩下的就简单了。将 \(x'_j,y'_j\) 取反，按照 \(x\) 为关键字将 \((x_i,y_i)\) 排序并遍历，找出最大的 \(x'_j+y'_j\) 满足 \(x_i\ge x'_j,y_i\ge y'_j\) 即可。