14357: 【原4357】Chika and Pack

题目

题目描述

author: Li Zitong 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4357

Description

Chika学过一个著名的算法问题————背包问题。她也有一个很大的背包，有一天她想用这个背包把很多物品装进去。

这些物品最开始时被分成了n堆，她决定先把所有物品合成一堆。

合并总共需要进行n-1次，每一次合并，Chika可以把两堆物品合并到一起，消耗的体力等于两堆物品的重量之和。可以看出，合并结束后，物品就只剩下一堆了。Chika在合并物品时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些物品都塞到背包里，所以Chika在合并物品时要尽可能地节省体力。假定已知每个物品重量都为1，并且已知物品的堆数和每堆物品的数目，你的任务是设计出合并的次序方案，使Chika耗费的体力最少，并输出这个最小的体力耗费值。

例如有三堆物品，数目依次为2，3，9。可以先将1、2堆合并，新堆的数目为5，耗费体力为5。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为14，耗费体力为14。所以Chika总共耗费体力为5+14=19。可以证明19为最小的体力耗费值。

Input Format

输入文件包括两行，第一行是一个整数 n (1 <= n <= 100000)，表示开始时物品的堆数。第二行包含 n 个整数，用空格分隔，第 i 个整数ai（1 ≤ ai ≤ 100000）是第 i 堆物品的数目。

Output Format

输出文件包括一行，这一行只包含一个整数，也就是最小的体力耗费值。

提示：int的范围是-2^31 ~ 2^31-1。

Sample Input 1

3
2 3 9

Sample Output 1

19

Sample Input 2

5
5 4 3 2 1

Sample Output 2

33

satgo1546's solution

#include <cstdio>
using namespace std;

int n;
// 二叉堆上节点索引 ∈ [1, n]。
unsigned long long a[100007];
unsigned long long s;

void insert(unsigned long long x) {
    n++;
    a[n] = x;
    int i = n;
    while (i > 1 && a[i / 2] > a[i]) {
        unsigned long long tmp = a[i];
        a[i] = a[i / 2];
        a[i / 2] = tmp;
        i /= 2;
    }
}

void down_heapify(int i) {
    while (i * 2 <= n) {
        int j = i * 2;
        if (i * 2 + 1 <= n && a[i * 2] > a[i * 2 + 1]) j++;
        if (a[i] > a[j]) {
            unsigned long long tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i = j;
        } else {
            break;
        }
    }
}

unsigned long long extract() {
    unsigned long long r = a[1];
    a[1] = a[n];
    n--;
    down_heapify(1);
    return r;
}

int main(int argc, char **argv) {
    scanf("%d", &argc);
    while (argc--) {
        unsigned long long x;
        scanf("%llu", &x);
        insert(x);
    }
    while (n > 1) {
        unsigned long long x = extract();
        x += extract();
        s += x;
        insert(x);
    }
    printf("%llu\n", s);
    return 0;
}