← 全部題目
Solved UVa 解題

Shopaholic

UVa 11369 UVa Online Judge ↗

每組送最便宜的那件，所以貴的要跟貴的湊一組；降序排序後取第 3、6、9… 個，貴的即為答案。

Greedy Sorting
Attempts3
First attempt2026-09-14
Solved2026-09-21

Problem

題目說 Lindsay 是個購物狂。只要看到「買三付二」的優惠（帶三件去結帳、只付兩件的錢），她就會失控地想把整間店買下來。你治不好她的強迫性購物症，不過卻能想辦法幫她的錢包止血（嗎？）

規則的關鍵有兩點：

  • 結帳時店家會把商品每 3 件分成一組，然後送掉每組裡最便宜的那一件。

  • 不過店家允許 Lindsay 可以分很多次結帳，而且自己決定每次帶哪些商品，也就是說結帳前可以精打細算來最大化折扣的總金額！

然後題目最後要問的是：你最多能幫 Lindsay 省下多少錢？

輸入第一行是測資組數 tt，每組測資兩行：商品數 nn，以及 nn 個價格。限制為 1≤t≤201 \le t \le 20、1≤n≤200001 \le n \le 20000、1≤pi≤200001 \le p_i \le 20000。


Approach

每組送掉的是最便宜的那件，因此如果要讓折扣金額變大，就要讓每組的最小值盡量大。

反過來想更清楚：如果把一件貴的商品跟兩件便宜的湊一組，那件貴的就只是在湊人數，送出去的卻是便宜貨，它的價值被浪費了。所以正確做法是由大到小排序，每 3 件切一組。

降序排序：400、350、300、250、200、150、100第 1 組400 · 350 · 300第 2 組250 · 200 · 150第 3 組100（湊不滿 3 件）最大折扣 = 300 + 150 = 450 送 300送 150送 0

整題就化約成一句話：降序排好後，把 arr[2]、arr[5]、arr[8]… 加起來就是答案。


Wrong attempts

我第一次是升序排序，然後想「起點要看 nn 的奇偶」：

第一版（WA）
sort(arr, arr + n);


bool is_even = false;
if (n % 2 == 0) {
    is_even = true;
}


if (is_even) {
    for (int j = 0; j < n; j += 3) {
        if (arr[j] == 0) break;
        max_discount += arr[j];
    }
} else {
    for (int j = 1; j < n; j += 3) {
        if (arr[j] == 0) break;
        max_discount += arr[j];
    }
}

錯在決定起點的是 n mod 3n \bmod 3，不是 n mod 2n \bmod 2。

升序陣列裡免費的是 index n−3,n−6,n−9,…n-3, n-6, n-9, \dots 一路往回走，走到最小的那個下標就是 n mod 3n \bmod 3。所以升序版的正確寫法只有一行：

升序版的正確起點
bool is_even = (n % 2 == 0);
for (int j = (is_even ? 0 : 1); j < n; j += 3)
for (int j = n % 3; j < n; j += 3)
    max_discount += arr[j];

奇偶判斷只在某些 nn 剛好對上，這就是為什麼它能通過我手上的測資：

nnn mod 3n \bmod 3（正確起點）我的起點（奇偶）結果
600（偶）✅ 巧合
711（奇）✅ 巧合
410（偶）❌
521（奇）❌
820（偶）❌

官方 sample 是 n=6n = 6、題敘的例子是 n=7n = 7，兩筆都剛好巧合。我只拿這兩組測，所以當然測不出來就 WA 了。

Solution

想通之後改成降序排序、從 index 2 起跳每次加 3，一次就過了。

main.cc
6 collapsed lines
#include <iostream>
#include <algorithm>
#include <functional>   // greater<int>


using namespace std;


void solve() {
    int t, n;
    int arr[20005] = {0};


    cin >> t;
    while (t--) {
        cin >> n;
        for (int j = 0; j < n; j++) cin >> arr[j];


        sort(arr, arr + n, greater<int>());


        int max_discount = 0;
        for (int j = 2; j < n; j += 3) {
            max_discount += arr[j];
        }


        cout << max_discount << '\n';
    }
}


8 collapsed lines
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    solve();


    return 0;
}

被標起來的四行就是全部的演算法：排序，然後從 j=2j = 2 開始每次跳 3 格。

Sample Input

sample.in
1
6
400 100 200 350 300 250

Sample Output

sample.out
400

驗算：排序後是 400、350、300、250、200、100400、350、300、250、200、100，取 index 2 和 5 得 300+100=400300 + 100 = 400，答案正確。

錯誤歷程

  1. WA用 n % 2 判斷升序起點，只拿題目範例驗證#1
  2. WA同樣的奇偶邏輯，改了細節但還是錯#2
  3. AC改成降序排序，每 3 個取第 3 個，自己多測了幾個測資#3

See also