TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

98.6% (216/219)

Submission's AC Ratio

50.1% (355/708)

Tags

Description

你剛剛解決了有人委託給你的「木材切割問題」,結果...

是的,身邊太多蘿莉也是會出事情的。
「我要3份喔膩醬!!」
「我要2份我要兩份!!」
「啊啊啊!!住手啊啊啊啊!」
---以下為自動屏蔽內容---

現在有N隻小蘿莉,每隻蘿莉想要ai份,令L= $ \sum_{i=1}^ {n}ai$,不妨假設你全身上下剛好可以等分成L單位吧,你要把這L單位拆成a1,a2,...,aN(不一定要按照順序)單位分送給各個蘿莉。
不過如果你將你一塊x單位的身體拆成兩塊你會恰好感到x單位的痛苦度,請問你至少會感到多少痛苦度以完成蘿莉的需求呢?
舉例來說,假設你身體分為10單位,而有4隻蘿莉分別想要2,2,3,3單位,考慮以下兩種切割方式。
第一種:
{10} 將10單位分成8,2。
{8,2} 將8單位分成6,2。
{6,2,2} 將6單位分成3,3。
{3,3,2,2} 完成,痛苦度為10+8+6=24。
第二種:
{10} 將10單位分成6,4。
{6,4} 將6單位分成3,3。
{4,3,3} 將4單位分成2,2。
{3,3,2,2} 完成,痛苦度為10+6+4=20。

而第二種也是所有切法裡最佳的。

Input Format

本題有多筆測資,請讀取到EOF結束。
對於每筆測資,
第一行有一個正整數N表示有N隻蘿莉。
第二行有N個以空格間隔的正整數ai依序表示第i隻蘿莉想要的單位數。

所有測資 : |ai|≤104

測資組A : N≤6
測資組B : N≤20
測資組C : N<51
測資組D : N≤1000
測資組E : N≤105

Output Format

對於每筆測資輸出一行,每行一個整數表示最小的痛苦度。

Sample Input 1

4
3 2 2 3
5
2 3 4 5 10
5
2 4 5 7 10

Sample Output 1

20
52
62

Hints

正當蘿莉拿起美工刀時,你醒了,發現只是一場夢而已。

Problem Source

Subtasks

No. Testdata Range Score
1 0 6
2 1 20
3 2 1
4 3 46
5 4 27

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5