贪心每次选最小的两堆合并即可。 注意STL自带的优先队列是大根堆，排序是降序排列，升序需要把缺省的比较函数换成greater（也是STL自带）
#include <cstdio> #include <queue> using namespace std; int n,a[10010],ans=0; priority_queue<int, vector<int>, greater<int> > q; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); q.push(a[i]); } for(int i=1;i<=n-1;i++){ int temp=q.top(); q.pop(); temp+=q.top(); q.pop(); q.push(temp); ans+=temp; } printf("%d",ans); return 0; }顺便学习一下优先队列的基本方法
#include<queue> using namespace std; //优先队列的声明 priority_queue<int> q1; //从小到大排序的优先队列 priority_queue<int, vector<int>, greater<int> > q2; //自定义结构体的优先队列 priority_queue<node> q3; bool operator < (node a1, node a2){ return a1.x<a2.x ? true : false; { //或者把operator定义在结构体内部 struct Node{ int x, y; Node(int a=0, int b=0): x(a), y(b) {} friend operator <(Node a,Node b){ if(a.x==b.x) return a.y>b.y; return a.x>b.x; } };剩下的把queue里面的front()换成top()就好啦
顺便贴一道母题《均分纸牌》的代码（超简单）
#include <cstdio> using namespace std; int n,a[200]; int main(){ int ans=0,sum=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum+=a[i]; } int avg=sum/n; for(int i=1;i<=n;i++) { if(a[i]!=avg){ ans++; a[i+1]-=(avg-a[i]); } } printf("%d\n",ans); return 0; }转载于:https://www.cnblogs.com/leotan0321/p/6081413.html
