UVa 11369 - Shopaholic

( Tip: 點擊左上方的三橫槓選單按鈕，可以收起左側 Pdf 頁。)

Step 1. 題目概要

  • 有間商店舉辦優惠活動，活動的方法是買三件物品而其中最便宜的一件不用錢，問最多可以省多少錢。

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

  • 第一行是測試筆數T(1 ≤ T ≤ 20)。每筆測試有兩行輸入。第一行是林希買的商品數n(1 ≤ n ≤ 20000)。下一行則是這些商品的價格pi(1 ≤ pi ≤ 20000)。
  • 每個測試，輸出一行，印出如果林希適當地分次結帳時所能省下的最大金額。

Step 2. 解題思路

  • 使用貪婪演算法(Greedy)
  • 將數據從大到小排序，每次取前三個物品，可以省下其中最便宜的，此方法即為最省錢的方法
  • 先利用sort函數，將價格由大到小進行降序排列
  • 接著把所有價格看成三個三個一組，其中每組的第三筆價格就是可以被省下的金額

Step 3. 範例輸入與輸出 - Sample Input and Output

1
2
3
1
6
400 100 200 350 300 250
1
400

Extra Sample Input
Extra Sample Output

uDebug 快速連結
Diffnow (線上比對程式)
C++ Online Compiler
Python Online Compiler

Step 4. 參考程式碼 - Accepted Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin>>T;
    while(T--) {
        int n;
        cin>>n;
        int pi[n];
        //inpiut
        for(int i=0; i<n; i++)
            cin>>pi[i];
        //calculate
        int sum=0;
        sort(pi,pi+n,greater<int>());  //降序排列
        for(int i=2; i<n; i+=3)
            sum+=pi[i];
        //output
        cout<<sum<<"\n";
    }
    return 0;
}