我觉得我就是一个整合小能手！以下全是我搜来的关于优先队列的事情。。。。。
最近做一道题，我一直以为和石子的合并一摸一样，就一直按照区间dp的方法写一道题，结果一直错一直错一直错，我还死不悔改一直交认为自己没错，就是下边这道题。
xiaok大佬最近再雇佣工人给他掰木棒。把一根长为L的木棒锯成两段，他需要支付给工人L元钱。xiaok大佬一开始只有长为L的一根木棒，他想把它锯成n段，每段长度分别为L1,L2,...,Ln，问xiaok大佬最少要付给工人多少钱？
其实他和石子合并不一样，石子合并的顺序是不可以变的，这个可以变，只要最后锯出来要求长度的木棒就可以了啊！
于是我就了解了优先队列！嘿嘿嘿撞了无数次南墙多学到了一种方法。
首先了解以下什么是优先队列（这个不看也行） https://www.sohu.com/a/256022793_478315
其次就是优先队列啦 https://www.cnblogs.com/garychen97/p/13778035.html
最后就是容器！ https://blog.csdn.net/gogokongyin/article/details/51178378
我觉得优先队列就是一个队列，不过普通的队列是先入先出，而优先队列是按照一定的优先级出。
就比如我自己束缚住自己的这道题
xiaok大佬最近再雇佣工人给他掰木棒。把一根长为L的木棒锯成两段，他需要支付给工人L元钱。xiaok大佬一开始只有长为L的一根木棒，他想把它锯成n段，每段长度分别为L1,L2,...,Ln，问xiaok大佬最少要付给工人多少钱？
第一行两个整数n,L(1<n<103,n<L<109)
第二行n个整数L1,L2,...,Ln（0<Li<L,且保证L1+L2+...+Ln=L）
输出一个整数，表示最小花费
这题的解决方法就是最小代价，跟合并石子的思路一样，不过注意这个可以变换位置而石子堆不可以换位置，这也就是我一直错的原因QAQ！！！
#include<iostream> #include<queue> using namespace std; typedef long long ll; priority_queue<int,vector<int>,greater<int> >Q;//我定义了一个从小到大的优先队列 //把greater改为less就是从大到小了。注意最后的>>中间要加个空格不然编译器会认为它是cin>> int main() { int n,l; cin>>n>>l; int t; for(int i=0;i<n;i++) { cin>>t; Q.push(t);//放进去它就会自动排序了 } ll x,y; ll sum=0; while(Q.size()>1) { x=Q.top();//输出的顶部就是所有数中最小的数啦 Q.pop(); y=Q.top(); Q.pop(); ll he=x+y; sum+=he; Q.push(he);//放进去一个数这个队列就会重新排队 } cout<<sum; return 0; }
