题解 P1090 【合并果子】

· · 题解

证明不断取最小的两堆合并成较大的一堆是最优的。

（不太好证哦）

①最优方案可以表示成一个二叉树。总代价 \sum_{i=1}^{n} a_i × depth_i。其中 depth 是深度，也就是这堆果子在整个过程中被有效合并了几次。

注意：a_i 都是叶子结点。非叶子结点都是合并后的产物。

②最小的两堆一定在最优方案树的最深层。

这个用反证法。假设有一个最优方案树，其最深层中没有最小的两堆。那么把最小的堆与最深层的某堆互换位置形成新方案，保证新方案存在而且新方案的代价小于原方案。

注意：最深层总是一组（一组有两个）或多组叶子节点，来表示它们被直接合并。

③同层叶子节点互换，对总代价无影响。

根据①的 \sum 得。可见，最小的两堆，如果在最优方案树最深层中不是即将合并的一组，那么可以无偿换为一组。

④根据上两步，我们已经明确：最优方案需要直接合并当前最小的两堆。现在我们就进行这个操作。事实是：现在只剩 n-1 堆了。我们只知道刚才进行了一个绝对不错的操作，而不记得操作之前是什么样的。我们只想对现在剩下的几堆陌生的果子进行最好的操作。忽略之前的树，于是回到①了。

注意：这并不意味着之前一步的操作使日后的代价和非常优秀。

#include <cstdio>
#include <queue>
using std :: priority_queue;
using std :: greater;
using std :: vector;

int n, ans = 0;
priority_queue < int, vector <int>, greater <int> > q;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
        int x; scanf("%d", &x);
        q.push(x);
    }
    while(q.size() > 1)
    {
        int x = q.top(); q.pop();
        int y = q.top(); q.pop();
        ans += x + y;
        q.push(x + y);
    }
    printf("%d\n", ans);
    return 0;
}

这些说法是不对的：

一、每步取最小的两堆合并成较大的两堆，能保证形成“这一步代价最小”且“接下来将要消耗的代价比其它方案小”。

反例如，如果有四堆果子，数目分别是3,4,5,6。然而我选择合并5,6，虽然目前代价很大，但你会发现接下来的代价比“先合并3,4，接下来的代价”要小得多。这否定了一些题解。

二、如果给初始的每堆果子 a_i 记录一个 t_i 表示这堆果子在整个过程中相当于合并了几次，那么 t_i 的和是定值。

其实方案不同的时候， t_i 之和完全可以变化。可以是 n^2 级别，也可以是 n~logn 级别。这导致上面的证明更难。

这道题可视作构造哈夫曼树。而对哈夫曼树正确性的证明让很多人头疼，《Algorithms》也是大花笔墨！所以证明可能真的不是那么简单。

有更简单的证明、或者上面的证明有问题，就评论吧！