TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (9/9)

Submission's AC Ratio

76.9% (10/13)

Tags

uva

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

4
2
3
4
7

Sample Output 1

8

Sample Input 2

5
2000
1999
2000
2001
1999

Sample Output 2

1

Sample Input 3

5
2000
2000
2001
1999
1999

Sample Output 3

4

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10
10 10000 65536 262144 11
11 10000 65536 262144 12
12 10000 65536 262144 13