【NOIP2004】【Luogu1090】合并果子

problem

• 有n堆果子
• 每次可以将两堆果子合并，代价为新堆的果子数。
• 求把所有果子合并成一堆的最小代价。

solution

• 每次合并最小的两堆
• 用堆或者两个队列维护

证明？反证法。

codes

#include<iostream>
#include<queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> >q;
int main(){
    int n, ans = 0;  cin>>n;
    for(int i = 0; i < n; i++){
        int a;  cin>>a;  q.push(a);
    }
    for(int i = 0; i < n-1; i++){
        int a = q.top(); q.pop();
        int b = q.top(); q.pop();
        ans += a+b;  q.push(a+b);
    }
    cout<<ans;
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80398475