题解 | #[NOIP2004]合并果子#

一题两解

第一种，用队列

#include<bits/stdc++.h>
using namespace std;
int a[100100];
queue<int> p1, p2;

int main()
{
    int n;
    cin >> n;
    for( int i=1; i<=n; i++ )
    {
        cin >> a[i];
    }
    sort(a+1, a+1+n);
    for( int i=1; i<=n; i++ )
    {
        p1.push(a[i]);
    }
    int sum = 0;
    for( int i=1; i<=n-1; i++ )
    {
        int a, b;
        if( (p2.empty() ) || ( !p1.empty() && p1.front()<p2.front()) )
        {
            a = p1.front();
            p1.pop();
        }
        else {
            a = p2.front();
            p2.pop();
        }
        if( (p2.empty() ) || ( !p1.empty() && p1.front()<p2.front()) )
        {
            b = p1.front();
            p1.pop();
        }
        else {
            b = p2.front();
            p2.pop();
        }  
        
        p2.push(a+b);
        sum = sum +a +b;
        
    }
    cout <<sum;
    return 0;
}

第二种 用优先队列，也是一种特殊的二叉树，c++自带priority_queue;

#include<bits/stdc++.h>
using namespace std;
priority_queue<int> q;
int main()
{
    int n;
    cin >> n;
    for( int i=1; i<=n; i++ )
    {
        int t;
        cin >> t;
        q.push(-t);  ///注意这里priority_queue的排序是从大到小的即top（）为最大的数。
    }
    long long sum=0;
    for( int i=1; i<n; i++)
    {
        int a1=-q.top();
        q.pop();
        int a2=-q.top();
        q.pop();
        int t = a1+a2;
        sum = sum +t;
        q.push(-t);
    }
    cout <<sum;
    return 0;
}