题目

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

输入描述：
第一行一个数n表示原序列的长度；
接下来一行n个数a_i表示原序列的第i个数。
2<=n<=100000
0<=a[i]<=10000

输出描述：
一行一个整数表示答案。

解析

1）知识点

这道题，简单贪心。

2）看题目

题目意思就是让你找到最大花费的划分方法。

3）算法分析

最大花费，你要不贪心要不就dp呗。这道题明显贪心能解决。
我们简单的就来看一下怎么才能让你花费的最多呢？
你第一次一定都是全部的，如果你要让第二次最大，你就只能尽量删掉小的。同理，第二次到第三次也要尽量删掉小的。
那么我们每次删掉最小的就好了。然后排成逆序求前缀和之和不就好了？（sum[1]就相当于最后一次删除的情况）

4）算法操作

  1. 操作就简单了。
  2. 拍个序： 
    sort(info + 1, info + 1 + n, greater<int>());
  3. 求前缀和： 
    for (int i = 1; i <= n; i++) sum[i] = info[i] + sum[i - 1];
  4. 求前缀和之和： 
    ll ans = 0;
for (int i = 2; i <= n; i++) ans += sum[i];
cout << ans << endl;

5）打代码

  1. 所以嘛，先输入。
  2. 然后排序。
  3. 然后求前缀和。
  4. 然后求和。
  5. 然后输出。
  6. 看我代码哈哈哈哈嗝~

AC代码 

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e5 + 7;
int info[MAX], sum[MAX];
//全局变量区

int main() {
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> info[i];
    sort(info + 1, info + 1 + n, greater<int>());
    for (int i = 1; i <= n; i++) sum[i] = info[i] + sum[i - 1];
    ll ans = 0;
    for (int i = 2; i <= n; i++) ans += sum[i];
    cout << ans << endl;
    return 0;
}
//函数区