贪心与优先队列：最小化加法代价问题

问题描述

给定一组正整数，你需要通过不断选取其中的两个数进行相加，并将结果重新放入集合中，直到所有数合并为一个。每次相加的代价是两个被加数之和。你的任务是找到一种加法顺序，使得总的加法代价最小。

输入格式

每个测试用例以一个正整数 N (2 ≤ N ≤ 5000) 开始，表示接下来有 N 个正整数（每个数小于 100000）。当 N 为 0 时，表示输入结束，该情况不需要处理。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示最小的总加法代价。

样例输入

3
1 2 3
4
1 2 3 4
0

样例输出

9
19

解题思路

要使总加法代价最小，可以使用贪心策略：每次选择当前集合中最小的两个数进行相加。具体实现上，可以使用优先队列（最小堆）来高效地获取和维护当前最小的两个元素。

代码实现

使用 multiset 实现：

#include 
#include 
using namespace std;
multiset vec;

int main() {
    int num;
    while (cin >> num && num) {
        int key;
        vec.clear();
        for (int i = 0; i             cin >> key;
            vec.insert(key);
        }
        int sum = 0;
        while (vec.size() >= 2) {
            auto it1 = vec.begin();
            int x = *it1;
            vec.erase(it1);
            it1 = vec.begin();
            int y = *it1;
            vec.erase(it1);
            sum += x + y;
            vec.insert(x + y);
        }
        cout <    }
    return 0;
}

使用优先队列实现：

#include 
#include 
using namespace std;

struct node {
    int x;
    bool operator<(const node& a) const {
        return x > a.x;
    }
};

priority_queue pq;

int main() {
    int n, sum = 0;
    while (scanf("%d", &n) != EOF && n) {
        sum = 0;
        for (int i = 0, x; i             scanf("%d", &x);
            pq.push({x});
        }
        while (pq.size() > 1) {
            int x = pq.top().x;
            pq.pop();
            int y = pq.top().x;
            pq.pop();
            sum += x + y;
            pq.push({x + y});
        }
        printf("%d\n", sum);
    }
    return 0;
}