[题解]GarsiaWachs算法

· · 题解

[做法] 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

例：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
\infty 186 67 64 103 \infty 2 1
\infty 186 131 103 \infty 2 -1
\infty 234 186 \infty 1 -1
\infty 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

查找预期比较次数是 ${\sum_{j=1}^n p_j(level+1)+{\sum_{k=0}^n}q_k(level_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} ，则已经将一棵最优树转变成为另一颗了

#### 引理二，树的旋转调整分支高度 假定 $j$ 和 $k$ 是满足 $j \lt k$ 的下标，并且满足 1. 对于 $1\le i\lt k,q_{i-1} \gt q_{i+1}
  1. q_{k-1} \le q_{k+1}
  2. 对于 j \le i \lt k-1,q_i \lt q_{k-1} + q_k
  3. q_{j-1} \ge q_{k-1} + q_k

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

a. l_j=l_k-1 证明方法，从引理一直到 $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 有

于是，对于 $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 这个分支上升

#### 引理三，加西亚瓦克斯算法核心 如上所述，可以考虑删除 $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 的级别

    ​ $i,\ldots,k-2,x$ 替换序列 $x,i,\ldots,k-2 ​ $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 快敲死我了

    终