【练习】Cut
Cut
https://ac.nowcoder.com/acm/problem/14291
题目
题目描述：给你一个长度为n的序列，你每次可以将一个序列分割成两个连续的的子序列，
分割的代价为原序列的总和。
现在允许你在初始时将序列重新排列一次。
问分割成n个长度为1的序列的最大总代价是多少？
第一行一个数n表示原序列的长度；
接下来一行n个数a_i表示原序列的第i个数。
2<=n<=100000
0<=a[i]<=10000
一行一个整数表示答案。
解析
1）知识点
这道题，简单贪心。
2）看题目
题目意思就是让你找到最大花费的划分方法。
3）算法分析
最大花费，你要不贪心要不就dp呗。这道题明显贪心能解决。
我们简单的就来看一下怎么才能让你花费的最多呢？
你第一次一定都是全部的，如果你要让第二次最大，你就只能尽量删掉小的。同理，第二次到第三次也要尽量删掉小的。
那么我们每次删掉最小的就好了。然后排成逆序求前缀和之和不就好了？（sum[1]就相当于最后一次删除的情况）
4）算法操作
- 操作就简单了。
- 拍个序：
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;
5）打代码
- 所以嘛，先输入。
- 然后排序。
- 然后求前缀和。
- 然后求和。
- 然后输出。
- 看我代码哈哈哈哈嗝~
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;
}
//函数区牛客算法竞赛入门课题解 文章被收录于专栏
憨憨的专栏
Momenta公司福利 296人发布
