题意
一个长度为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; }