果子合并：贪心算法实现最小体力消耗

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1 ，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 3种果子，数目依次为 1， 2， 9 。可以先将 1 、 2堆合并，新堆数目为 3 ，耗费体力为 3 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为 12 。所以多多总共耗费体力 =3+12=15 。可以证明 15 为最小的体力耗费值。

输入格式

共两行。

第一行是一个整数 n(1≤n≤10000)，表示果子的种类数。

第二行包含 n个整数，用空格分隔，第 i个整数 a i a_iai是第 i种果子的数目。

输出格式

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 2 32 2^{32}232

输入输出样例

输入 #1

1 2 9

输出 #1

说明/提示

对于30％的数据，保证有n≤1000：

对于50％的数据，保证有n≤5000；

对于全部的数据，保证有n≤10000。

算法实现

算法1

(贪心+优先队列) $O(nlogn)$

首先，根据哈夫曼编码的思想，我们应该优先选择小堆进行合并，因为合并后的堆的大小更大，可以使得之后的合并操作中所需要的体力更少。

因此，我们可以使用一个小根堆来维护所有的果堆，每次取出两个最小的堆进行合并，并将合并后的堆重新放回小根堆中。由于每次合并都是选择最小的两个堆进行，因此可以保证最终的合并顺序一定是最优的。

时间复杂度

对于每个果堆，都需要进行一次插入操作，共需要插入n个堆，因此插入的总时间复杂度为$O(nlogn)$。每次合并操作需要取出两个堆，因此需要进行n-1次合并，每次合并需要取出两个堆，再将合并后的堆插入优先队列中，因此每次合并的时间复杂度为$O(logn)$。因此，总时间复杂度为$O(nlogn)$。

C++ 代码

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        heap.push(a);
    }
    int ans = 0;
    while (heap.size() > 1) {
        int a = heap.top();
        heap.pop();
        int b = heap.top();
        heap.pop();
        ans += a + b;
        heap.push(a + b);
    }
    cout << ans << endl;
    return 0;
}

算法2

(贪心+线段树) $O(nlogn)$

我们可以将当前所有堆的大小看做线段树上的节点，线段树上每个节点维护的信息为该节点所表示的区间内所有堆的大小之和。初始时，每个叶子节点的值即为对应果堆的大小。

接下来，我们每次需要找到当前最小的两堆进行合并，那么这两堆对应的线段树上的节点，应该分别是区间最小值和次小值对应的节点。找到这两个节点后，将它们的值相加，并将新的值赋给区间最小值对应的节点，然后将次小值对应的节点标记为无效节点。这样，我们就完成了一次合并操作，并且在合并过程中，只需要修改线段树上最多4个节点的值。

最终，所有果堆都合并到了一起，我们只需要求出线段树的根节点的值，即为最小的体力耗费值。

时间复杂度

线段树上每个节点最多被修改一次，因此总时间复杂度为$O(nlogn)$。

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 10000;

int tree[MAXN * 4], lazy[MAXN * 4], val[MAXN];
bool valid[MAXN];

void pushup(int rt) {
    tree[rt] = tree[rt * 2] + tree[rt * 2 + 1];
}

void pushdown(int rt, int l, int r) {
    if (lazy[rt] != 0) {
        int mid = (l + r) / 2;
        tree[rt * 2] += lazy[rt] * (mid - l + 1);
        tree[rt * 2 + 1] += lazy[rt] * (r - mid);
        lazy[rt * 2] += lazy[rt];
        lazy[rt * 2 + 1] += lazy[rt];
        lazy[rt] = 0;
    }
}

void build(int rt, int l, int r) {
    if (l == r) {
        tree[rt] = val[l];
        return;
    }
    int mid = (l + r) / 2;
    build(rt * 2, l, mid);
    build(rt * 2 + 1, mid + 1, r);
    pushup(rt);
}

void update(int rt, int l, int r, int ql, int qr, int val) {
    if (ql <= l && qr >= r) {
        tree[rt] += val * (r - l + 1);
        lazy[rt] += val;
        return;
    }
    pushdown(rt, l, r);
    int mid = (l + r) / 2;
    if (ql <= mid) update(rt * 2, l, mid, ql, qr, val);
    if (qr > mid) update(rt * 2 + 1, mid + 1, r, ql, qr, val);
    pushup(rt);
}

int query(int rt, int l, int r, int ql, int qr) {
    if (ql <= l && qr >= r) {
        return tree[rt];
    }
    pushdown(rt, l, r);
    int mid = (l + r) / 2;
    int ans = 0;
    if (ql <= mid) ans += query(rt * 2, l, mid, ql, qr);
    if (qr > mid) ans += query(rt * 2 + 1, mid + 1, r, ql, qr);
    return ans;
}

int find_min(int rt, int l, int r) {
    if (l == r) {
        return l;
    }
    pushdown(rt, l, r);
    int mid = (l + r) / 2;
    int min_l = find_min(rt * 2, l, mid);
    int min_r = find_min(rt * 2 + 1, mid + 1, r);
    if (tree[rt * 2] < tree[rt * 2 + 1]) return min_l;
    else return min_r;
}

int find_second_min(int rt, int l, int r, int min_pos) {
    if (l == r) {
        if (l != min_pos) return l;
        else return -1;
    }
    pushdown(rt, l, r);
    int mid = (l + r) / 2;
    int second_min_l = -1, second_min_r = -1;
    if (min_pos <= mid) {
        second_min_r = find_second_min(rt * 2 + 1, mid + 1, r, min_pos);
        if (tree[rt * 2] < tree[rt * 2 + 1]) second_min_l = find_min(rt * 2, l, mid);
        else second_min_l = find_second_min(rt * 2, l, mid, min_pos);
    } else {
        second_min_l = find_second_min(rt * 2, l, mid, min_pos);
        if (tree[rt * 2] > tree[rt * 2 + 1]) second_min_r = find_min(rt * 2 + 1, mid + 1, r);
        else second_min_r = find_second_min(rt * 2 + 1, mid + 1, r, min_pos);
    }
    if (second_min_l == -1) return second_min_r;
    if (second_min_r == -1) return second_min_l;
    if (tree[rt * 2] < tree[rt * 2 + 1]) return second_min_l;
    else return second_min_r;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
        valid[i] = true;
    }
    build(1, 1, n);
    int ans = 0;
    while (valid[find_min(1, 1, n)]) {
        int min_pos = find_min(1, 1, n);
        int second_min_pos = find_second_min(1, 1, n, min_pos);
        ans += tree[1];
        update(1, 1, n, min_pos, min_pos, tree[1]);
        update(1, 1, n, second_min_pos, second_min_pos, -tree[1]);
        valid[second_min_pos] = false;
    }
    cout << ans << endl;
    return 0;
}