Cut

题目描述

链接：https://ac.nowcoder.com/acm/problem/14291

给你一个长度为n的序列，你每次可以将一个序列分割成两个连续的的子序列， 分割的代价为原序列的总和。
现在允许你在初始时将序列重新排列一次。
问分割成n个长度为1的序列的最大总代价是多少？

输入描述

第一行一个数n表示原序列的长度；
接下来一行n个数a_i表示原序列的第i个数。
2<=n<=100000
0<=a_i<=10000

输出描述：

一行一个整数表示答案。

solusion：

这题属于贪心，将一个序列分成两个连续的序列，可以先将序列重排，所以可以将对这个序列最小的值先给分出来

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100005];
long long s=0;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<n-1;i++)
        s=s+a[i]*(i+1);
    s=s+a[n-1]*(n-1);
    cout<<s;
}