题解

思路

把全部 $2n$ 个数排序为 $b_0\le b_1\le\cdots\le b_{2n-1}$。

任意从左上角到右下角的路径都经过 $n+1$ 个格子，且恰好在某一列向下。对一个已经排好的网格，令上行前缀和为 $P_i$，下行从第 $i$ 列开始的后缀和为 $S_i$，乌龟获得的能量就是

$$\max_{1\le i\le n}(P_i+S_i).$$

存在一个最优排列，使最小的两个数 $b_0,b_1$ 分别位于左上角和右下角。其余 $2n-2$ 个数被分为大小均为 $n-1$ 的两组 $X,Y$。把 $X$ 升序接在上行的 $b_0$ 后，把 $Y$ 降序放在下行的 $b_1$ 前，则每个下转位置对应的值都不超过

$$b_0+b_1+\max\left(\sum X,\sum Y\right),$$

而在最左或最右下转时能取到两组和中的较大者。因此原题等价于：从剩下的数中恰好选 $n-1$ 个，使选中和与未选和的较大者最小。

做法

子任务 1：直接枚举

当 $n\le10$ 时，递归枚举剩余 $2n-2$ 个数中所有大小为 $n-1$ 的子集，计算两组和并保留最优集合。

子任务 2：折半搜索

当 $n\le18$ 时，把剩余数分为左右两半。枚举右半所有子集，按选取个数分类并按和排序。枚举左半子集后，设还需选 $k$ 个，在对应右半列表中二分最接近总和一半的位置。检查二分点及其前驱即可得到最优划分。

满分做法：按个数的子集和

设 reachable[c] 是一个位集合，第 $s$ 位为一表示可以从已经处理的数中恰好选 $c$ 个且和为 $s$。初始只有 reachable[0][0]=1。处理权值 $w$ 时倒序更新

$$\text{reachable}[c]\mathrel{|}=\text{reachable}[c-1]\ll w.$$

最终扫描 reachable[n-1] 中的可达和，选择使 $\max(s,T-s)$ 最小的 $s$，其中 $T$ 是剩余数字总和。为恢复具体集合，对每个首次到达的状态记录最后加入的数字编号，然后从最优状态倒推。

最后按“左上角为 $b_0$、上行其余升序、下行前段降序、右下角为 $b_1$”输出。

正确性证明

首先考虑任意排列。左上角与右下角被每一条路径经过，所以把这两个位置的数与其他位置较大的数交换不会降低其他格子可供路径选择的贡献；反复交换后，可得到一个不劣的排列，使这两个位置放置最小的两个数。

固定端点后，上行其余格子与下行其余格子形成两个大小均为 $n-1$ 的集合。若上行内部按非降序、下行内部按非升序排列，那么下转列从左向右移动时，路径只会把一个较小的下行元素替换成一个不小于它的上行元素。所有下转路径的能量夹在两端下转路径之间，最大值恰为端点和加两组总和的较大者。

因此，任意大小合法的二分组都能构造出目标值 $b_0+b_1+\max(\sum X,\sum Y)$ 的排列；反过来两条边界路径分别包含端点和两组中的全部元素，任何排列的最强路径都不小于该较大者。原题故与等大小两组的最平衡划分完全等价。

三种算法分别完整枚举、折半枚举或动态规划所有“恰选 $n-1$ 个”的可达和，所以都会找到该表达式的最小值。按上述单调顺序输出后达到这个下界，故输出最优。

复杂度

直接枚举时间复杂度为 $O\!\left(\binom{2n-2}{n-1}n\right)$，空间复杂度为 $O(n)$。

折半搜索时间复杂度为 $O(2^n n)$，空间复杂度为 $O(2^n)$。

满分做法令 $V=\sum b_i\le2{,}500{,}000$，时间复杂度为 $O(nV/64+nV)$，空间复杂度为 $O(nV)$；位集合负责转移，逐和父指针负责恢复方案。