题库-CF|【Codeforces Round 263 (Div 2)C】【贪心哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权贪心|CodeForces

Appleman and Toastman time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output 【题库-CF|【Codeforces Round 263 (Div 2)C】【贪心哈弗曼思维】Appleman and Toastman 每个非1size子树延展为2子树的最大权】 Appleman and Toastman play a game. Initially Appleman gives one group of n numbers to the Toastman, then they start to complete the following tasks:

Each time Toastman gets a group of numbers, he sums up all the numbers and adds this sum to the score. Then he gives the group to the Appleman.
Each time Appleman gets a group consisting of a single number, he throws this group out. Each time Appleman gets a group consisting of more than one number, he splits the group into two non-empty groups (he can do it in any way) and gives each of them to Toastman.

After guys complete all the tasks they look at the score value. What is the maximum possible value of score they can get?
Input The first line contains a single integer n (1?≤?n?≤?3·105). The second line contains n integers a1, a2, ..., an (1?≤?ai?≤?106) — the initial group that is given to Toastman.
Output Print a single integer — the largest possible score.
Examples input

3 3 1 5

output

26

input

1 10

output

10

Note Consider the following situation in the first example. Initially Toastman gets group [3, 1, 5] and adds 9 to the score, then he give the group to Appleman. Appleman splits group [3, 1, 5] into two groups: [3, 5] and [1]. Both of them should be given to Toastman. When Toastman receives group [1], he adds 1 to score and gives the group to Appleman (he will throw it out). When Toastman receives group [3, 5], he adds 8 to the score and gives the group to Appleman. Appleman splits [3, 5] in the only possible way: [5] and [3]. Then he gives both groups to Toastman. When Toastman receives [5], he adds 5 to the score and gives the group to Appleman (he will throws it out). When Toastman receives [3], he adds 3 to the score and gives the group to Appleman (he will throws it out). Finally Toastman have added 9 + 1 + 8 + 5 + 3 = 26 to the score. This is the optimal sequence of actions.

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x,y) memset(x,y,sizeof(x)) #define MC(x,y) memcpy(x,y,sizeof(x)) #define MP(x,y) make_pair(x,y) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template inline void gmax(T1 &a, T2 b) { if (b>a)a = b; } template inline void gmin(T1 &a, T2 b) { if (b= 1; --i)s[i] = s[i + 1] + a[i]; LL ans = s[1]; for (int i = 1; i < n; ++i)ans += s[i]; printf("%lld\n", ans); } return 0; } /* 【题意】有一组数，组内n（3e5）个数字a[]，（1<=a[]<=1e6），操作1，累积：对于每组数，我们得到这些数字之后，我们会把所有数字的和累积。操作2，分组：然后，如果这些数字只有一个，这组数就结束了。否则，我们会把这组数分成两组，继续重复操作1。问你我们最后能得到的最大的数字是多少【类型】贪心脑洞【分析】比赛的时候，我感觉每次分组都丢掉最小的一个。这种感觉是对的，我们通过前缀和优化，写完就直接AC了。然而为什么呢？我们可以把问题考虑为一棵树的形状变化初始有1个节点，size为n。每次我们每个size不为1的节点，都需要向下扩展2个分支，两个分支的size之和为其父节点的size。然后让你求这棵树的权值之和。如果按照题目规则衍生分枝，我们会发现，其实分枝的个数必然是一定的。（3->4，4->6，5->8）我们肯定希望大的权走尽可能多的分枝数。于是这里显然采取如此策略。【时间复杂度&&优化】 O（n）【数据】 5 3 1 9 5 3 1 5 31 8 1 5 38 5*/