官方题解（中文整理）

基于 Charlie Yang 的官方题解整理。

先理解第二阶段的最优策略

每次把两个桶合并，最终会形成一棵二叉树。原数组中的每个 \(a_i\) 会以某个系数贡献到最终答案中，这个系数是 \(2^{-d_i}\)，其中 \(d_i\) 是它在合并树中的深度。

因此，要让最终值尽量大，就应该让较大的数拥有尽量小的深度，也就是尽量晚被合并。

这意味着：第二阶段的最优策略，本质上总是优先把较小的元素合并掉。于是最终最优结果只与元素大小的相对顺序有关。

进一步可以推出：若想达到全局最大值，阶段 1 排序后的数组应当呈现“先单调不增，再单调不减”的形态，也就是一个谷形数组。这样最小的元素总能彼此相邻并优先被合并。

所以问题就转化成：

• 把原数组通过最少相邻交换，变成一个谷形数组

二值子任务

当所有 \(a_i\) 只可能是 \(0\) 或 \(1\) 时，问题更简单。

如果 \(0\) 的个数不超过 \(1\)，答案显然是 \(0\)。

否则，想要在第二阶段尽快把所有 \(0\) 合并掉，就需要把所有 \(0\) 通过相邻交换挪到一起，形成一段连续区间。

于是问题变成：把所有 \(0\) 聚成一段，最少要多少次相邻交换。

朴素做法可以枚举这段区间的位置，复杂度 \(O(N^2)\)；进一步利用中位数性质，可以在线性时间内算出最优代价。

一般情况的关键转化

设我们按数值从小到大处理元素。

对某个元素来说，在最终谷形排列中，它只能放到“当前已经放好的更小元素”的左侧或者右侧。若把它放到左边，需要跨过左边那些比它小的元素；放到右边也是类似。

于是，对每个元素，我们只需比较两种代价：

• 把它放到谷的左侧：代价等于它左边比它小的元素个数
• 把它放到谷的右侧：代价等于它右边比它小的元素个数

取两者较小值即可。

注意，相等的元素之间无须区分先后，因此处理某个值时，必须先对这一整组相等元素统一计算代价，再整体加入数据结构。

如何快速维护“比当前元素小”的位置分布

如果维护一个 01 数组：

• 某位置是已经处理过的更小元素，则记为 \(1\)
• 否则记为 \(0\)

那么对当前位置 \(i\)：

• 左侧更小元素个数就是前缀和
• 右侧更小元素个数就是总和减去前缀和

这可以用树状数组或线段树在 \(O(\log N)\) 时间内维护。

做法如下：

1. 按值从小到大遍历所有元素位置
2. 对于当前值的所有位置，先查询各自左边和右边已经出现了多少更小元素
3. 把较小者加入答案
4. 等这一组相同值全部处理完后，再把这些位置加入树状数组

复杂度

排序复杂度 \(O(N \log N)\)，每个位置进行常数次树状数组操作，故总复杂度为：

\(O(N \log N)\)

可以通过全部数据。