1237 . 砍了那些腳 Cut Many Legs
TopCoder
Tags
Description
不知道你有沒有寫過UVA online judge的Cut the Legs?
那題是這麼說的:
試想一個一般有四隻腳的圓桌，如果有一隻腳比其他三隻稍微短了一點，則這桌子就會搖晃
這時候一個解決的辦法，是把其他三隻腳都鋸得跟最短那隻一樣長，這樣桌子就不會晃了!
現在有一個有n隻腳的圓桌，其中每隻腳均勻分布在圓周上
你可以假設這些桌腳都沒有重量，而桌面有重量並且是密度均勻的
給定這n隻腳的長度，試問至少要鋸掉多少總長度的桌腳，才能使最後的桌子不會傾斜也不會晃?
所謂不會傾斜的定義，是說桌面平行地面
不會晃的定義，是說假設不施外力，桌子不會翹向另一邊；但注意像上面那種3長1短的情形是歸類為會晃的
這題並不困難，不過我覺得原先的測資有點虛弱(n<=50)
噢不，是我這邊剛好有個36798隻桌腳的桌子需要平衡，用那O(n^4)的程式跑實在是太緩慢了
麻煩你寫個程式幫忙解決。
Input Format
每個input只有一組測試資料
第一行有一個整數n，代表總共有幾支桌腳
接下來n行有n個整數，分別(依序)代表桌腳的長度。
3 <= n <= 2,000,000
桌腳長度皆在int的範圍。
Output Format
請輸出一個整數，代表最少要砍掉多少長度的桌腳
Sample Input 1
2
3
4
7
Sample Output 1
Sample Input 2
2000
1999
2000
2001
1999
Sample Output 2
Sample Input 3
2000
2000
2001
1999
1999
Sample Output 3
Hints
嘿嘿...你的程式可能要超級有效率, 才能通過測試資料!
不過其實這..我也不大確定啦XDrz
這只是邪惡的出題者的單方面希望而已XDDD
當然，這也意謂著，如果你有AC的決心，請愛用快速的I/O函式
(例如scanf, printf)
※範例輸出/輸入增補，第二筆範例測資中，只要將2001截短為2000，桌子就可以站得穩了。但是在第三筆範例測資就不行。
Problem Source
原TIOJ1237 / Adapted from UVa Online Judge, Problem Setter: kelvin, tmt514
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 7 |
| 2 | 1 | 7 |
| 3 | 2 | 7 |
| 4 | 3 | 7 |
| 5 | 4 | 7 |
| 6 | 5 | 7 |
| 7 | 6 | 7 |
| 8 | 7 | 7 |
| 9 | 8 | 7 |
| 10 | 9 | 7 |
| 11 | 10 | 7 |
| 12 | 11 | 7 |
| 13 | 12 | 16 |