文章
36
粉丝
505
获赞
55
访问
372.5k
题目很容易看出贪心策略:每次只合并最小的两堆
但是每次合并后的堆还要放回去,得保证放回去后数据依旧有序
这里介绍一种数据结构:优先队列,头文件#include <queue>
这个队列弹出元素不是按照入队的先后,而是按照权值的大小出队。
定义:
priority_queue<int> q; 定义队列q,权值大的先出队
priority_queue <int, vector<int>, greater<int> > q;权值小的先出队
#include<bits/stdc++.h>
using namespace std;
priority_queue <int, vector<int>, greater<int> > q;
int main()
{
int n, x, ans = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> x;
q.push(x);
}
for (int i = 1; i < n; i++)
{
int a = q.top();
q.pop();
int b = q.top();
q.pop();
ans += a + b;
q.push(a + b);
}
cout << ans;
return 0;
}
登录后发布评论
暂无评论,来抢沙发