ZeroJudge D150: Shopaholic

同題:UVa 11369 – Shopaholic

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

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

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

範例測資

範例輸入範例輸出
第一行是測試筆數 1 ≤ T ≤ 20。每筆測試有兩行輸入。第一行是林希買的商品數 1 ≤ N ≤ 20000。下一行則是這些商品的價格 1 ≤ Pi ≤ 20000。每個測試,輸出一行,印出如果林希適當地分次結帳時所能省下的最大金額。
1
6
400 100 200 350 300 250
400

解題思路

每個商品的價錢收到一個 Vector 中,收完之後使用 Sort

For迴圈,從最大跑到最小,以每三個為單位,並將目前位置減 2 的價錢加到答案中。

範例程式碼-ZeroJudge D150: Shopaholic

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 0; i<T; i++)
    {
        int N;
        cin >> N;
        vector<int>num;
        for (int j = 0; j<N; j++)
        {
            int tmp;
            cin >> tmp;
            num.push_back(tmp);
        }
        sort(num.begin(), num.end());
        int ans = 0;
        for (int j = N-1; j>=0; j--)
        {
            if (j - 2 < 0) break;
            else
            {
                ans += num[j-2];
                j -= 2;
            }
        }
        cout << ans << "\n";
    }
}

//ZeroJudge D150
//Dr. SeanXD

發佈留言