修补栅栏

Grade 100 Open Time Wednesday, 17 June 2020, 5:25 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 5:25 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 5:25 PM
Input file repair.in Output file repair.out

【题目描述】修补栅栏(repair)POJ 3253

院长家后花园的栅栏坏了,他测量了栅栏,发现需要N(1≤N≤20 000)块木板,每块木板为长度Li(1≤Li≤50 000)的整数。他买了一块长得足以锯成N块木板的长板(也就是说,它的长度是长度Li的总和,不考虑锯木板时的额外损失)。

但是锯木板的代价正好等于它的长度,例如锯一块长度为21的木板要花费的代价为21。问如何安排锯木板的顺序,使得花费的总代价最小。

【输入格式】

第一行为一个整数N。随后N行,每行一个整数,代表每块木板长度。

【输出格式】

输出一个数,即最小代价。

【输入样例】

3

8

5

8

【输出样例】

34

【样例说明】

先从无限长的木板上锯下长度为 21 的木板,花费 21;

再从长度为21的木板上锯下长度为5的木板,花费5;

再从长度为16的木板上锯下长度为8的木板,花费8;

总花费=21+5+8=34