这道题用哈夫曼树做, 使用 STL 中的优先队列.
优先队列:
- #include <queque>
- // 升序
- priority_queuqe <int,vector<int>,greater<int>> q;
- // 在 q 前面需要空一格, 否则就是右移.
- priority_queque <int,vector<int>,Less<int>>q;
- // 降序, 也可不写, 默认.
- q.push(a) // 将 a 压入栈
- q.top() ;// 取出栈顶元素
- q.pop(); // 栈顶指针减一.
- q.size() ;// 队列中有几个元素.
原理思想是: 当一直在合并两个最小堆时消耗值最小, 所以就是用哈夫曼树, 因为一直是最小的, 所以最后算的值也最小.
- #include <iostream>
- #include <cstdio>
- #include <queue>
- using namespace std;
- // 使用优先队列完成, 使用到霍夫曼数
- int n;
- const int MAXN=10000;
- int a[MAXN];
- int main()
- {
- priority_queue <int,vector<int>,greater<int>>q; // 必须加上 gteater<int>
- scanf("%d",&n);
- int sum=0;
- for(int i=0; i<n; i++)
- {
- scanf("%d",&a[i]);
- q.push(a[i]);
- }
- while(q.size()>1)
- {
- int a=q.top();
- q.pop();
- int b=q.top();
- q.pop();
- q.push(a+b);
- sum+=(a+b);
- }
- printf("%d",sum);
- return 0;
- }
我的错误:
1. 忘了优先队列默认是从大到小的, 一直在算最大值.
来源: http://www.bubuko.com/infodetail-3280589.html