[洛谷 1090,poj 3253][NOIP2004]合并果子

题目链接

https://www.luogu.org/problem/P1090

http://poj.org/problem?id=3253

题解

可以证明，将果子最少的两堆合并起来可以使得总体力消耗值最小。

于是我们可以建立一个堆（或者是优先队列），每次取出堆顶的两个元素，合并后重新放入堆，并更新结果。

下面的程序手写了一个小根堆：

#include <cstdio>
#include <algorithm>
using namespace std;
int heap[1000005],cnt,ans;
void up(int p)
{
 while(p>=1&&heap[p]<heap[p/2])
 {
  swap(heap[p],heap[p/2]);
  p/=2;
 }
}
void down(int p)
{
 int s=p*2;
 while(s<=cnt)
 {
  if(s<cnt&&heap[s]>heap[s+1])s++;
  if(heap[s]<heap[p])
  {
   swap(heap[s],heap[p]);
   p=s;
   s=p*2;
  }
  else break;
 }
}
void insert(int x)
{
 heap[++cnt]=x;
 up(cnt);
}
int top()
{
 return heap[1];
}
void pop()
{
 heap[1]=heap[cnt--];
 down(1);
}
int main()
{
 int n;
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
 {
  int a;
  scanf("%d",&a);
  insert(a);
 }
 while(cnt!=1)
 {
  int newa=0;
  ans+=top();
  newa+=top();
  pop();
  ans+=top();
  newa+=top();
  pop();
  insert(newa);
 }
 printf("%d",ans);
 return 0;
}