#551. 合并果子

_#551. 合并果子

方法一：手写堆

（题解->陶）

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+10;
int n,heap[maxn],size=0;
void up(int p) //二叉小根堆向上调整（子节点小于父节点就调整）
{
  while(p>1)
  {
    if(heap[p]<heap[p/2])
    {
      swap(heap[p],heap[p/2]);
      p/=2;
    }
    else break;
  }
}
void insert(int val) //二叉堆插入，新元素放在堆底，向上调整
{
  heap[++size]=val;
  up(size);
}
void down(int p) //二叉小根堆向下调整
{
  int s=p*2;
  while(s<=size)
  { //下面这句话是从左右儿子中选一个更小的做交换
    if(s<size&&heap[s+1]<heap[s]) s++; 
    if(heap[s]<heap[p])
    {
      swap(heap[s],heap[p]);
      p=s; s=p*2;
    }
    else break;
  }
}
void extract() //二叉堆删除堆顶
{
  heap[1]=heap[size--]; //将堆底移至堆顶，向下调整
  down(1);
}
int gettop() //返回堆顶的值
{
  return heap[1];
}
int main()
{
  cin>>n;
  for(int i=1; i<=n; i++)
  {
    int a; cin>>a;
    insert(a); //建立二叉堆
  }
  long long ans=0; //其实这里不会越界，但好像原题数据是3万
  while(size>=2) //如果还可合并
  {
    int top1=gettop(); //取出堆顶（堆中最小值）后删除堆顶
    extract();
    int top2=gettop(); //同上
    extract();
    ans+=(top1+top2);
    insert(top1+top2); //将两数之和加入二叉堆，重复运算
  }
  cout<<ans<<endl; //输出答案
  return 0;
}

方法二：STL

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int main(){
	priority_queue<int,vector<int>,greater<int> >dui;
	cin>>n;
	for(int i=1;i<=n;i++){
		int cii;
		cin>>cii;
		dui.push(cii);
	}
	for(int i=1;i<n;i++){
		int a=dui.top();
		dui.pop();
		int b=dui.top();
		dui.pop();
		dui.push(a+b);
		ans+=a+b;
	}
	cout<<ans;
	return 0;
}