你剛剛解決了有人委託給你的「木材切割問題」,結果...
是的,身邊太多蘿莉也是會出事情的。
「我要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。
而第二種也是所有切法裡最佳的。
本題有多筆測資,請讀取到EOF結束。
對於每筆測資,
第一行有一個正整數N表示有N隻蘿莉。
第二行有N個以空格間隔的正整數ai依序表示第i隻蘿莉想要的單位數。
所有測資 : |ai|≤104
測資組A : N≤6
測資組B : N≤20
測資組C : N<51
測資組D : N≤1000
測資組E : N≤105
對於每筆測資輸出一行,每行一個整數表示最小的痛苦度。
正當蘿莉拿起美工刀時,你醒了,發現只是一場夢而已。
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 6 |
2 | 1 | 20 |
3 | 2 | 1 |
4 | 3 | 46 |
5 | 4 | 27 |