Enter $\looparrowright$

Description

Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs $N$ $(1 ≤ N ≤ 20000)$ planks of wood, each having some integer length $L_i (1 ≤ L_i ≤ 50000)$ units. He then purchases a single long board just long enough to saw into the $N$ planks (i.e., whose length is the sum of the lengths $L_i$ ). FJ is ignoring the “kerf”, the extra length lost to sawdust when a sawcut is made; you should ignore it, too.
FJ sadly realizes that he doesn’t own a saw with which to cut the wood, so he mosies over to Farmer Don’s Farm with this long board and politely asks if he may borrow a saw.
Farmer Don, a closet capitalist, doesn’t lend FJ a saw but instead offers to charge Farmer John for each of the $N-1$ cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length $21$ costs $21$ cents.
Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.

Input

Line $1$ : One integer $N$ , the number of planks
Lines $2$ to $N+1$ : Each line contains a single integer describing the length of a needed plank

Output

Line $1$ : One integer: the minimum amount of money he must spend to make $N-1$ cuts

Sample Input

3
8
5
8

Sample Output

Hint

He wants to cut a board of length $21$ into pieces of lengths $8, 5$ , and $8$ .
The original board measures $8+5+8=21$ . The first cut will cost $21$ , and should be used to cut the board into pieces measuring $13$ and $8$ . The second cut will cost $13$ , and should be used to cut the $13$ into $8$ and $5$ . This would cost $21+13=34$ . If the $21$ was cut into $16$ and $5$ instead, the second cut would cost $16$ for a total of $37$ (which is more than $34$ ).

Translation

我们要将将一根很长的木条切成 $N$ 份，每份的长度为 $L_i$ ，未切割前木条的长度为 $\sum\limits_{i=1}^NL_i$ 。每次切断木条时，需要的开销为这根木条的长度，如将一根长度为 $21$ 的木条分割成 $x$ 和 $21-x$ 的两部分，开销为 $21-x+x=21$ 。请求出按照目标要求将模板切割完最小的开销是多少。

Idea

如果我们需要将一根木条分成长度为 $a,b$ 的两份，那么开销就是 $a+b$ ，我们可以定义将两根长度为 $a,b$ 的木条拼成一根的开销也为 $a+b$ 。对于题目的情境，每一次将某一根木条切成两根的开销，相当于将两根木条合并成一根。因此，可以将题目看成是把 $N$ 段木条拼成一根，每次拼的代价为所拼木条的长度和。
显然，越早拼好的木条其产生开销的机会就越多。例如有三根木条长度分别为 $a,b,c$ ，如果选择先拼 $a,b$ ，那么产生的总开销为 $(a+b)+[(a+b)+c]=2a+2b+c$ 。因此贪心的策略是每次选取两个最小的来拼，可以用优先队列实现。时间复杂度为 $O(n\log n)$

Code

#include<iostream>
#include<queue>
#include<cstdio>
#define ll long long 
using namespace std;
int main()
{
	int n;
	cin>>n;
	priority_queue<ll,vector<ll>,greater<ll> >q;
	int i;
	for(i=1;i<=n;i++)
	{
		ll temp;
		scanf("%lld",&temp);
		q.push(temp);
	}
	ll ans=0;
	for(i=1;i<=n-1;i++)//切n-1刀，进行n-1次拼接
	{
		//每次取最短的两根
		ll first_minimun=q.top();
		q.pop();
		ll second_minimun=q.top();
		q.pop();
		ans=ans+first_minimun+second_minimun;
		q.push(first_minimun+second_minimun);//重新推进队列
	}
	cout<<ans<<endl;
	return 0;
}