d150. 11369 - Shopaholic
標籤 :
通過比率 : 1513人/1627人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-03-11 22:57

內容

林希是個購物狂。每次只要有買二送一的折扣,她就像瘋了一樣要買下店裡所有的商品。你已經放棄治療她的病了,但是想減少她的支出。

你知道買二送一所送的一定是結帳商品中最便宜的那幾樣。比如說,你的朋友拿了價值為 400, 350, 300, 250, 200, 150, 及 100 的七樣商品到櫃枱去結帳,她就得付 1500 元。她省下了最便宜的兩樣商品的價錢,也就是 250 元。如果她分三次去結帳,她可以省下更多的錢。比如說,她先拿 400, 300 和 250 的去結,第一次就可以省下 250 元。第二次她只拿 150 元的去結,沒有折扣。但是第三次她拿 350, 200, 和 100 的去結,又省了 100 元,總共省下了 350 元。

你的工作便是找出林希最多可以省多少錢。

輸入說明

第一行是測試筆數 1 ≤ 𝑡 ≤ 20。每筆測試有兩行輸入。第一行是林希買的商品數 1 ≤ 𝑛 ≤ 20000。下一行則是這些商品的價格 1 ≤ 𝑝𝑖 ≤ 20000。

輸出說明

每個測試,輸出一行,印出如果林希適當地分次結帳時所能省下的最大金額。

範例輸入 #1
1
6
400 100 200 350 300 250
範例輸出 #1
400
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
提示 :

原題

標籤:
出處:
UVa11369 [管理者: snail (蝸牛) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」