百力滋交换

对于任意高度 $t$，只连接高度不超过 $t$ 的围墙。费用不超过 $t$ 的一对必须在同一连通分量内，大小为 $s$ 的分量中至多能配出 $\lfloor s/2\rfloor$ 对。按围墙高度递增处理，在每个分量内尽可能配对，人数为奇数时留下一人。高度为 $h$ 的围墙合并两个奇数大小的分量时，将留下的两人配对并增加费用 $h$；其他情况不新增配对。两人之间的最大围墙高度恰好为 $h$。该构造对每个阈值 $t$ 都同时达到费用不超过 $t$ 的配对数量上界。因此将配对费用排序后，每一项都不大于其他完美匹配的对应项，总和也最小。排序和并查集的时间复杂度为 $O(N\log N)$，空间为 $O(N)$。子任务 $1$ 可用子集 DP，枚举剩余编号最小的人的配对对象，时间上界为 $O((2N)^2 2^{2N})$。

Solution written by GPT6.1