ZeroJudge 解題筆記：d150. 11369 - Shopaholic

作者：王一哲
日期：2026年4月21日


ZeroJudge 題目連結：d150. 11369 - Shopaholic

解題想法

先將價格由大到小排序存入串列 $prices$，每次取 $3$ 項，將第 $3$ 項加入答案 $ans$。也可以用最大優先佇列，將價格全部存入最大優先佇列 $pq$，每次從 $pq$ 彈出目前的最高價格，每彈出 $3$ 個值就將第 $3$ 個值加入答案 $ans$。因為這題不需要一直將值推入 $pq$ 之中，可以用排序就好，速度比較快。

Python 程式碼

使用時間約為 12 ms，記憶體約為 10.9 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        t = int(data[ptr])
        ptr += 1
        for _ in range(t):
            n = int(data[ptr])
            ptr += 1
            prices = sorted(map(int, data[ptr:ptr+n]), reverse=True)
            ptr += n
            ans = sum(p for p in prices[2::3])
            result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 16 ms，記憶體約為 11.1 MB，通過測試。

def solve():
    import sys, heapq

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        t = int(data[ptr])
        ptr += 1
        for _ in range(t):
            n = int(data[ptr])
            ptr += 1
            pq = []
            for __ in range(n):
                p = int(data[ptr])
                ptr += 1
                heapq.heappush(pq, -p)
            ans, cnt = 0, 0
            while pq:
                p = -heapq.heappop(pq)
                cnt += 1
                if cnt == 3:
                    ans += p
                    cnt = 0
            result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 3 ms，記憶體約為 3.1 MB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    int t;
    while(scanf("%d", &t) != EOF) {
        for(int i=0; i<t; i++) {
            int n;
            scanf("%d", &n);
            vector<int> prices (n);
            for(int j=0; j<n; j++) {
                scanf("%d", &prices[j]);
            }
            sort(prices.begin(), prices.end(), greater<int>());
            int ans = 0;
            for(int j=2; j<n; j+=3) {
                ans += prices[j];
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

使用時間約為 3 ms，記憶體約為 3.2 MB，通過測試。

#include <cstdio>
#include <queue>
using namespace std;

int main() {
    int t;
    while(scanf("%d", &t) != EOF) {
        for(int i=0; i<t; i++) {
            int n;
            scanf("%d", &n);
            priority_queue<int> pq;
            for(int j=0; j<n; j++) {
                int p;
                scanf("%d", &p);
                pq.push(p);
            }
            int ans = 0, cnt = 0;
            while(!pq.empty()) {
                int p = pq.top();
                pq.pop();
                cnt++;
                if (cnt == 3) {
                    ans += p;
                    cnt = 0;
                }
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}