###### tags: `APCS`
# **e591－Coin Collector**
### **題目連結：** [**e591**](https://zerojudge.tw/ShowProblem?problemid=e591)
### **題目解析**
Sultan 在一個國家旅行，該國家有 n 種不同面額的硬幣。當 Sultan 從銀行提取一筆金額時，銀行會根據如下規則發放硬幣：
1. 提款規則：
* 如果 Sultan 想提取 X 元，銀行會找到面額不超過 X 的最大硬幣 Y，然後把這個硬幣 Y 給 Sultan。
* 接下來，剩餘的金額變成 X - Y，銀行再對這個新的金額重複這個過程，直到所有金額都已發放完畢。
1. 目標：
* Sultan 想在一次提款中，獲得最多種類的不同面額的硬幣。
* 他可以選擇提取任意金額，只要能蒐集到最多種類的硬幣。
### **解題方向**
1. 貪心策略：
* 因為硬幣面額是遞增排列，所以在一次取款中，盡量選擇盡可能小的硬幣，這樣才能在之後選擇更多種類的硬幣。
* 在遍歷每一種硬幣時，如果累加現有的硬幣後不超過下一個面額，則選擇當前面額。
1. 步驟：
* 首先選擇最小面額的硬幣（這裡是 1），然後逐步累加後面的硬幣。
* 如果累加後的金額小於下一個硬幣的面額，那麼就可以選擇當前的硬幣。

### **程式解析**

for i in range(1, types - 1):

這一行表示遍歷硬幣面額的範圍是從第二個硬幣 `(i = 1)` 到倒數第二個硬幣 `(i = types - 2)`。這樣做的原因是：
1. 第一個硬幣 `(coin[0])` 和最後一個硬幣 `(coin[types - 1])` 是特殊情況，通常會直接選擇。
1. 中間的硬幣需要根據條件來決定是否選擇。

if collect < coin[i] and (collect + coin[i]) < coin[i + 1]:

這一行包含兩個條件：
1. `collect < coin[i]`: 這個條件檢查目前累積的硬幣總額 `collect` 是否小於當前遍歷到的硬幣 `coin[i]`。這樣可以確保選擇這個硬幣不會超過現有總額。
1. `(collect + coin[i]) < coin[i + 1]`: 這個條件檢查如果把當前硬幣` coin[i]` 加入到累積總額 `collect` 中，是否仍然小於下一個硬幣的面額 `coin[i + 1]`。這樣可以確保選擇這個硬幣後，下一個硬幣還是可以被選擇。
### **完整程式碼**

# 讀取測資數量
N = int(input())

for d in range(N):
    # 讀取不同類型的硬幣數量
    types = int(input()) 

    # 讀取硬幣的面額列表
    coin = list(map(int, input().split()))

    if types <= 2:
        # 如果只有兩種或以下的硬幣，則可以直接使用所有硬幣
        print(types)
    else:
        # 初始化選擇的硬幣數量
        collect = coin[0]  # 第一個硬幣一定會選擇
        c = 2  # 至少會選擇第一個和最後一個硬幣

        # 遍歷從第二個到倒數第二個硬幣
        for i in range(1, types - 1):
            # coin[i]要大於累加的collect且累加進collect後，collect要小於下一個值(coin[i+1])
            if collect < coin[i] and (collect + coin[i]) < coin[i + 1]:
                collect += coin[i]  # 累加當前硬幣面額
                c += 1  # 計數加一

        # 輸出結果
        print(c)