2018年4月8日星期日,小龙沉迷于一个叫做组合的游戏。

游戏规则是这样的,原本有一个长度为A的大木板,现在把它分成了n份长度可能不一样的木板。每一个模板的长度为Xi,每次游戏都要把这些木板组合为一个完整的木板,但是小龙每次只能拿两个小木板去组合成为一个,然后把这新木板和剩下的木板放在一起,重复以上步骤直到最后只剩下一个木板。

每次组合木板会花费K个金币,K等于拿起的两个木板长度之和,问小明每次玩游戏最少花费是多少?

例如:当有n=3块木板的时候

每一块木板的长度分别是是 1、2、3

第一次拿长度为1 和 2 的木板拼接成长度为3的木板,花费3个金币

此时有两块木板,长度分别为3 和 3

第二次拿长度为3 和3 的木板拼接成长度为6的木板,花费6个金币

总共花费9个金币(最少)。

输入格式

输入描述:

输入有多组,每一组第一行是n(1 < n <= 200)

接下来第二行到第n+1行,第i+1行表示小木板的长度Xi (Xi <= 200)

输出格式

输出描述:

输出每个样例的最少花费,每个答案占据一行。

示例

输入
3
1
2
3

输出
9

题目分析

经典的 Huffman树 问题, 需要注意的是,本题有多组测试数据。

本题数据范围较小, 使用 小根堆 或者 排序 + 贪心 都可以解决。

代码实现

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

int n, x;
int main()
{   
    while(cin >> n) {
        priority_queue<int, vector<int>, greater<int>> heap;
        while (n--) {
            cin >> x;
            heap.push(x);
        }
        int res = 0;
        while (heap.size() > 1) {
            int a = heap.top(); heap.pop();
            int b = heap.top(); heap.pop();
            res += a + b;
            heap.push(a + b);
        }
        cout << res << '\n';
    }
    return 0;
}
分类: HeapSort

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status