題目描述

您有N個木棍,每個木棍的長度是一個正整數。有一種切木棍的方式,每次都會將所有木棍切除相同的長度,切除的長度為當下要切除的木棍中最短的長度。



假設我們有六個木棍,長度分別是:

5 4 4 2 2 8

由於這裡最短的木棍長度是2,所以切除的長度為2。切除完長度為0的木棍就不管它,剩下的木棍長度分別是:

3 2 2 6

重複以上切除動作,直到所有木棍都被切個精光。

給定N個木棍的長度,輸出每次切除時將剩下的木棍數量。

原題網址

https://www.hackerrank.com/challenges/cut-the-sticks

輸入格式

第一行輸入整數N。

接下來的一行輸入N個整數,範圍是1到1000(包含1和1000),a0, a1,...,aN-1,ai為第i個木棍的長度,範圍是1到1000(包含1和1000)。

輸出格式

每次切除時將剩下來的木棍數量輸出至新的一行。

範例輸入1

6
5 4 4 2 2 8

範例輸出1

6
4
2
1

範例輸入2

8
1 2 3 4 3 3 2 1

範例輸出2

8
6
4
1

額外解釋

範例1:

範例2:

解題概念

由於這題需要去尋找最小值,而且也不需去管木棍原先的順序,因此可以將木棍的長度儲存在一個集合(如ArrayList)中,方便使用Collections類別提供的sort方法來排序。將集合排序之後,其最開頭的長度就是要切除的長度,接著將集合所有的元素值都去減掉這個長度,若減完後的長度為0,就將該元素從集合中移除。一直重複將所有元素減掉第一個元素的動作,直到集合內再也沒有元素,就完成所有的切除動作了。

參考答案