[HackerRank]切木棍(Cut the sticks)

題目描述

您有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,就將該元素從集合中移除。一直重複將所有元素減掉第一個元素的動作,直到集合內再也沒有元素,就完成所有的切除動作了。

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章