Cut

NC14291. Cut

描述

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

输入描述

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

输出描述

一行一个整数表示答案。

示例1

输入:

4
3 2 4 1

输出:

说明:

[3,2,4,1]重排->[1,2,3,4]->[1],[2,3,4]->[1],[2],[3,4]->[1],[2],[3],[4]。

示例2

输入:

4
1 1 1 1

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

pypy3 解法, 执行用时: 121ms, 内存消耗: 32016K, 提交时间: 2023-05-10 19:50:31

n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 0
for i in range(n):
    ans += a[i] * (i + 1)
print(ans - a[n-1])

Python3(3.5.2) 解法, 执行用时: 184ms, 内存消耗: 19284K, 提交时间: 2017-10-27 19:07:56

a,b=int(input()),list(map(int,input().split()))
b.sort()

print(sum(map(lambda c:b[c]*(c+1),range(a)))-b[-1])

详情