題目描述

您有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:

木棍的長度            要切除的長度      剩下木棍的數量
5 4 4 2 2 8             2               6
3 2 2 _ _ 6             2               4
1 _ _ _ _ 4             1               2
_ _ _ _ _ 3             3               1
_ _ _ _ _ _           DONE            DONE

範例2:

木棍的長度            要切除的長度      剩下木棍的數量
1 2 3 4 3 3 2 1         1               8
_ 1 2 3 2 2 1 _         1               6
_ _ 1 2 1 1 _ _         1               4
_ _ _ 1 _ _ _ _         1               1
_ _ _ _ _ _ _ _       DONE            DONE

解題概念

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

參考答案

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Solution {

    public static void main(final String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        final int n = sc.nextInt();
        final ArrayList<Integer> sticks = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            sticks.add(sc.nextInt());
        }
        Collections.sort(sticks);
        while (!sticks.isEmpty()) {
            final int size = sticks.size();
            final int min = sticks.get(0);
            for (int i = size - 1; i >= 0; --i) {
                int stick = sticks.get(i);
                stick -= min;
                sticks.remove(i);
                if (stick > 0) {
                    sticks.add(i, stick);
                }
            }
            System.out.println(size);
        }
    }
}