题解 P1090 【合并果子】

醉里挑灯看剑 · 2018-09-11 21:14:58 · 题解

这个题可以用堆来求

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int> q;
int n,a[100010],ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);//将所有的数全部取负这样的话绝对值小的数会变大，
        q.push(-a[i]);//绝对值大的会变小，以此建立一个小根堆
    }
    for(int i=1;i<n;i++)
    {
        int x=-q.top(); q.pop();
        int y=-q.top(); q.pop();
        ans+=x+y;//合并
        q.push(-x-y);
    }
    cout<<ans<<endl;
}