---
# System prepended metadata

title: d150－Shopaholic
tags: [APCS]

---

###### tags: `APCS`
# **d150－Shopaholic**
### **題目連結：** [**d150**](https://zerojudge.tw/ShowProblem?problemid=d150)
### **題目解析** 
題目要求我們找出林希在買二送一活動中，最多可以省下多少錢。買二送一的意思是，如果她買三樣商品，其中最便宜的一樣免費。這個情境下，我們需要找出最佳的結帳策略，使得她可以省下最多的錢。
### **解題方向** 
* 商品排序：將商品價格從高到低排序，因為這樣可以確保我們總是將最便宜的商品作為免費商品。
* 分組結帳：每次取三個商品，取第三個商品（也就是這三個中最便宜的）作為免費商品。
* 計算節省金額：累加所有這些免費商品的價格，並找出最大節省金額。

### **完整程式碼**
```python=
# 首先輸入測試資料的數量
t = int(input())

# 開始處理每筆測試資料
while t > 0:
    # 輸入每筆測試資料中的商品數量
    n = int(input())
    
    # 輸入商品價格並轉換成整數列表
    pi = input().split()
    pi = list(map(int, pi))
    
    # 將商品價格從高到低排序
    pi.sort(reverse=True)
    
    # 計算最大節省金額
    max_save = 0
    # 每次取三個商品，將最便宜的一個（第三個）作為免費商品
    for i in range(2, n, 3):
        #迴圈從 2 開始是因為我們在進行買二送一活動時，總是將最便宜的商品作為免費商品。在排序後的列表中，從最高價到最低價排序，第三個商品（也就是索引為2的商品）是這三個商品中最便宜的。
        max_save += pi[i]
    
    # 輸出最大節省金額
    print(max_save)
    
    # 減少測試資料計數
    t -= 1
```