最近胖胖國小又要舉辦園遊會了。
每年胖胖國小都會全校總動員,一起做一件有趣的事來做為園遊會的精神象徵與主題。
例如: 大胃王接力賽呀、環島接力馬拉松呀...,總之都會需要全校總動員才能夠達成。
今年胖胖國小則決定一起疊一個很大很大的羅漢,來做為這次活動的精神錦標。
現在全校的師生都已經站成一排了,為了平衡的關係,所以每個人頂多只被一個人踩。
不過為了防止跌倒,又為了防止最下面那層的人被壓死,所以可以扶著旁邊的欄杆。
因此對於某個人來說,除了受踩他的那個人的重量影響以外,不受更上層的人重量影響。
為什麼會指受踩他的那個人影響呢?因為假如你被一個比你胖的人踩,你當然會覺得很不爽囉XD!
因此A踩B,則A體重一定小於B。
不過事情還沒解決,因為這個隊伍實在是太長了,所以要重新整頓非常困難。
因此每個人的右腳只可能踩位置在他右邊的人,左腳只能踩位置在他左邊的人。
當然踩人不一定要踩兩個,只踩一個也是OK的。
而且假如某個人兩隻腳踩的人疊的高度不一樣也沒關係,因為最後他們都可以在地上墊東西以達成平衡。
不過為了減少隊伍動到,所以有一個規定是說:
當A原本在B左邊,且B現在在A上方時,B原本右邊的人,A都不能踩。
同樣的當A原本在B左邊,且A現在在B上方時,A原本左邊的人,B都不能踩。
當然對於每一種採法都會有穩定與不穩定的事情發生。
因此穩定度的估算是: 所有踩與被踩的人的體重差的平方和。
現在給你這n個人的體重(假設全部都不相同),問你說最穩定的穩定度為何?
輸入一數n(1<=n<=2000000)。
接下來有n個整數,每個數皆不超過int儲存範圍。
輸出一數代表最小穩定度的大小。
範例測資解釋:
總之堆積起來的圖會長這樣
因此最小穩定度是(2-1)2 + (3-2)2 + (4-3)2 + (5-1)2 + (6-5)2 + (7-6)2 + (8-7)2 + (9-5)2 = 38
※2009/7/23 補充題目敘述(by math120908): 感謝su_horng。
原TIOJ1549 / Problem Setter: math120908
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 20 |
2 | 1 | 20 |
3 | 2 | 20 |
4 | 3 | 20 |
5 | 4 | 20 |