1125 Chain the Ropes (25分)

题目链接：1125 Chain the Ropes (25分)

题意：

给出一些绳子的长度，将这些绳子两两结合起来，每次结合绳子长度为原来两个长度的一半，依题意结果向下取整。最终结合为一个绳子，求这个绳子的最大长度。

分析

哈夫曼编码。因为每次结合，都会使绳子长度减半，次数越多减得越多，因此让长的放在最后结合，减半的次数少，每次挑选最短的两个结合为一个新的长度，在从数组中挑选剩下的。可以用优先队列实现，最小的放前面，每次弹出两个值。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;int main(int argc, char** argv) {
    priority_queue<int, vector<int>, greater<int> > que;int n, x;scanf("%d", &n);for (int i = 0; i < n; i++) {
    scanf("%d", &x);que.push(x);}while (que.size() != 1) {
    int a1 = que.top();que.pop();int a2 = que.top();que.pop();que.push((a1 + a2) / 2);}printf("%d", que.top());return 0;
}