NC14291 Cut [贪心]+[堆]

题意

一个长度为n的序列，一次可将一个序列分割成两个连续的的子序列，分割的代价为原序列的总和，求分成n个子序列需要的最大代价。

题解

反过来思考，令其从n个长度为1的序列合成为一个长度为n的序列。每次合成代价为两序列之和。这时这道题就跟合并果子题十分相似了(合并果子)，只需将小根堆换成大根堆即可得到最大代价。
注意数据范围，需要开long long

Code

#include <bits/stdc++.h>
using namespace std;

priority_queue<long long> pq;   //大根堆

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 0;i < n;++i){
        long long tmp;
        scanf("%lld",&tmp);
        pq.push(tmp);
    }
    long long res = 0;
    while(pq.size() > 1){   //所剩序列在2个及以上
        long long a = pq.top();pq.pop();
        long long b = pq.top();pq.pop();
        res += a+b;         //合并
        pq.push(a+b);
    }
    printf("%lld\n",res);



    return 0;
}