自动搬运

查看原文

来自洛谷，原作者为

	Eastern 满船轻梦压星河，偷捧时间煮酒喝

搬运于2025-08-24 22:12:04，当前版本为作者最后更新于2020-02-20 09:38:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

[做法] GarsiaWachs算法

*更多内容及证明见后文

1. 找到满足 $q_{k-1} \lt q_{k+1}$ 的最小下标 $k$
2. 找到满足 $q_{j-1} \gt q_{k-1} + q_k$ 的最大 $j \lt k$
3. 从列表中清除 $q_{k-1}, q_k$
4. 在 $q_{j-1}$ 之后插入 $q_{k-1} + q_k$
5. $q_{-1}$ 和 $q_{n+1}$ 可以用 $\infty$ 处理

例：$q[5]=\{183,64,35,32,103\}$

$q_{-1}$	$q_0$	$q_1$	$q_2$	$q_3$	$q_4$	$q_5$	$k$	$j$
$\infty$	186	64	35	32	103	$\infty$	3	1
		67	64	103	$\infty$		2
		131	103	$\infty$				-1
	234	186	$\infty$				1
	420	$\infty$

代码实现： 通过 $vector$ 模拟上述过程

因为删除$erase$ 和 插入 $insert$ 操作速度较慢，代码需要O2优化 我太菜了

#include <bits/stdc++.h>//懒
using namespace std;

int n, k, j;
int ans, sum;
vector<int> v;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

int main()
{
    n = read();
    v.push_back(INT_MAX - 1);
    for (int i = 1; i <= n; i++)
        v.push_back(read());
    v.push_back(INT_MAX);

    while (n-- > 1)
    {
        for (k = 1; k <= n; k++)
            if (v[k - 1] < v[k + 1])
                break;
        sum = v[k] + v[k - 1];
        for (j = k - 1; j >= 0; j--)
            if (v[j] > v[k] + v[k - 1])
                break;
        v.erase(v.begin() + k - 1);
        v.erase(v.begin() + k - 1);
        v.insert(v.begin() + j + 1, sum);
        ans += sum;
    }
    
    printf("%d", ans);
    return 0;
}

加西亚-瓦克斯(GarsiaWachs)算法.

这种算法是基于最优二叉树提出的，有一个概念叫做

二叉树中预期比较次数

根节点的 $level = 0$

二叉查找树中给定几个概率值, $p_1, p_2,\ldots, p_n$ 和 $q_0, q_1, \ldots, q_n$

$p_i$ 表示查找参数是 $K_i$ 的概率， $q_i$ 表示查找参数介于 $p[K_i,K_i+1]$ 概率

查找预期比较次数是

${\sum_{j=1}^n p_j(level+1)+{\sum_{k=0}^n}q_k(level_k)}$

$q_k$ 针对外节点的，其实这理解起来也不难，外节点是直接暴露在外面的

根据只要知道它的层数，比如 $1,2$ 两个外节点都在第 $3$ 层，这时候只要

$3 \times q_1$ 就可以知道 $1$ 出现的概率，也就可以知道比较次数了

$p_j$ 是针对内节点的，一定要通过外节点才能进入内节点，所以要$level + 1$

上述公式叫 树的成本，预期比较次数为

外节点: $\{0,1,2,3\},2q_0+3q_1+3q_2+q_3$

内节点: $\{1,2,3\},2p_1+3p_2+p_3$

二者的和就是这个树的成本

加西亚瓦克斯算法就是上述树的成本中，$p_k = 0$ 时候的特例

$$c = \sum_{k=0}^nq_kl_k$$

引理一，最优二叉树的转化

如果 $q_{k-1} \gt q_{k+1}$，则在每棵最优树中，$l_k \le l_{k+1}$

如果 $q_{k-1} = q_{k+1}$，则在某些最优树中，$l_k \le l_k+1$

证明方法，看一个二叉树的剪裁

不妨设 $q_{k-1} \ge q_{k+1}$，并且考虑$l_k \gt l_{k+1}$

那么树的形状一定如上图所示，$k$ 为右孩子

这个时候如果按照图中的方式剪裁，两条线中的部分裁掉

让左子节点 $L$ 成为新的 $parent$ ，并且 $[l_k-1,l_{k+1}]$ 部分裁掉

使得 $k$ 节点上浮，并且 $k+1$ 节点下沉一个单位

不妨设 $L$ 是一个权值为 $w$ 的子树， $w \ge q_{k-1}$ ，这是显然的

因为我们假定 $q_{k-1} \ge q_{k+1}$ ，那么在左边的外节点权值更大

这样裁剪之后，总的权值变化包括 $3$ 个部分

1） $L$ 裁掉，$-w$}

2） $k$ 上浮，$-q_k(l_k-l_{k+1}-1)$

3） $k+1$下沉，$q_{k+1}$

$$\Delta = -w-q_k(l_k-l_{k+1}-1)+q_{k+1} \le -q_{k-1}-q_k(l_k-l_{k-1}-1)+q_{k+1}\le q_{k+1} - q{k-1} $$

如果 $q_{k+1}-q_{k-1}\lt0$ ，显然不是最优的，矛盾

另外，如果 $q_{k-1}=q_{k+1}$ ，则已经将一棵最优树转变成为另一颗了

$k-1$ 和 $k+1$ 这个层次上等价，$l_{k-1}=l_{k+1}$，构成最优树

引理二，树的旋转调整分支高度

假定 $j$ 和 $k$ 是满足 $j \lt k$ 的下标，并且满足

1. 对于 $1\le i\lt k,q_{i-1} \gt q_{i+1}$
2. $q_{k-1} \le q_{k+1}$
3. 对于 $j \le i \lt k-1,q_i \lt q_{k-1} + q_k$
4. $q_{j-1} \ge q_{k-1} + q_k$

于是，存在一颗满足 $l_{k-1}=l_k$ 的最优树，同时，它还满足以下条件之一

$a. l_j=l_k-1$

$b.l_j=l_k$ 且 $j$ 为左孩子

证明方法，从引理一直到 $q_{k-1} \le q_{k+1}$，存在满足 $l_{k-1}\ge l_k$ 的最优树

对于 $1 \le i \lt k$ 而言，还有 $l_1 \le l_2 \le \ldots \le l_k$，因此有 $l_{k-1}=l_k$

其次，我们关注树的层次，如下图所示

先看如图所示的三层结构，对于满足 $j \le s \lt k-1$ 的 $s$ 有

$l_s \lt l_k-1 \le l_{s+1}$，假设 $t$ 是满足 $l_t=l_k$ 且小于 $k$ 的最小下标

于是，对于 $s\lt i\lt t$ ，有 $l_i = l_k-1$ 并且 $s+1$ 为左孩子，或者

$s+1=t$，这样我们可以通过二叉树旋转等操作

让部分节点上升，部分节点下降

如果让s所在的分支下降，t所在的分支上升的话

$\Delta=q_s-q_t-q_t+1$，因为$t \lt k$，所以 $q_t\gt q_{k-1} \& q_{t+1} \gt q_k$

$\Delta=q_s-q_t-q_{t+1} \le q_s-q_{k-1}-q_k$

如果 $q_s\lt q_{k-1}+q_k$ ，所以 $\Delta \lt 0$ ，次时能得到更优的二叉树

旋转之后， $l_j \ge l_k-1$

再看最后一个部分，如果 $l_j=l_k$ 并且 $j$ 是有孩子的话，则一定有如下情况

如果旋转二叉树，让 $j-1$ 下降，让 $k-1,k$ 这个分支上升

$\Delta = -q_{j-1}+q_{k-1}+q_k \le 0$ ，此时二叉树并不是最优的，和假设矛盾

引理三，加西亚瓦克斯算法核心

如上所述，可以考虑删除 $q_{k-1}$ 和 $q_k$ 并且在 $q_{j-1}$ 之后插入 $q_{k-1}+q_k$

所得到的概率 $(q_0',\ldots ,q_{n-1}')=(q_0,\ldots,q_{j-1}, q_{k-1}+q_k,q_j,\ldots,q_{k-2},q_k+1,\ldots,q_n)$

于是，$C(q_0',\ldots,q_{n-1}')\le C(q_0,\ldots,q_n)-(q_{k-1}+q_k)$

排列方式

$0,\ldots,j-1,k-1,k,j,\ldots,k-2,k+1,\ldots,n$

更优

这就很简单了，根据引理二，如果是$b$类型的，只需要重命名这些叶节点就可以

如果是$a$类型的呢？可以通过旋转二叉树的方式，让 $(k-1,k)$ 这两个叶子对

上升一个高度，实际上就是在 $l_k$ 这个高度上，减掉 $q_{k-1}+q_k$ ，然后向左移动

在 $j-1$ 后面插入即可

引理四

任何一个排列方式如引理三所述的树，都可以转化成为

成本相同，叶子排列顺序为 $0,1,\ldots,n$ 的树

1. 如果 $j=k-1$ ，显然成立

2. 如果不相等，因为 $q_{j-1} \ge q_{k-1} + q_k \gt q_j$ (引理二条件)

   $0,\ldots,j-1,k-1,k,j,\ldots,k-2,k+1,\ldots,n$

                 ↑             ↑
   
                 j           k - 1 
   

   $q'$ 的下标表示如上所示，所以对于 $j \le i \le k-1$，有 $q_{i-1}' \gt q_{i+1}'$

   于是根据引理，有 $l_x \le l_j \le \ldots \le l_{k-2}$，其中 $l_x$ 是 $x$ 的级别，并且

   对于 $j \le i \lt k-1$，$l_i$ 是 $i$ 的级别

   $a.$ 如果 $l_x=l_{x-2}$，都在同一级上

   ​ $i,\ldots,k-2,x$ 替换序列 $x,i,\ldots,k-2$

   $b.$ 否则，假定 $l_s=l_x$，$l_{s+1}>l_x$，令 $l=l_x+1$，并且

   ​ $l$ 是节点 $(k-1,k)$ 的公共级别，使得

   ​ $l \le l_{s+1}\le \ldots\le l_{k-2}$，最后可以通过循环位移操作，使得

   ​ $k-1,k,s+1,\ldots,k+2$ 变成 $s+1,\ldots,k-2,k-1,k$

   有看不懂的别找我

   这个 $\LaTeX$ 快敲死我了

   终