小明的衣服-蓝桥1228-优先队列

本文主要是介绍小明的衣服-蓝桥1228-优先队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解法

用优先队列，思路参考哈夫曼树（贪心）

思路：很复杂，说结果

n件同色衣服要染成都不同色，求邮费最少；

倒过来想：n件不同颜色衣服，要染成同一种颜色，求邮费最少，所以贪心就是每次寄出两件邮费最少的两件衣服去染

如图所示：

代码

#include<iostream>
#include<queue>
using namespace std;typedef long long ll;//19位十进制
int main(){ll n;cin>>n;ll sum=0;priority_queue<ll,vector<ll>,greater<ll>> q;while(n--){ll a;cin>>a;q.push(a);}while(q.size()>1){ll a=q.top(); q.pop();ll b=q.top(); q.pop();ll c=a+b;sum+=c;q.push(c);//c进去，优先队列自动排序了}cout<<sum;return 0;
}

这篇关于小明的衣服-蓝桥1228-优先队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---