ZeroJudge 解題筆記：n688. pC. 卡牌遊戲

作者：王一哲
日期：2025年12月10日


ZeroJudge 題目連結：n688. pC. 卡牌遊戲

解題想法

先將卡牌分別正值、負值兩堆，為了將卡牌總和最大化，策略是將負值牌堆中最小的牌，也就是負值、量值最大的牌取出、轉為正值、存入正值牌堆，如果負值牌堆沒有資料了，就反過來將正值牌堆中最小的牌取出、轉為負值、存入負值牌堆。為了達成這個目標，用最小優先佇列儲存牌堆是最方便的。

Python 程式碼

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

import heapq

n, k = map(int, input().split())
positive, negative = [], []
for x in map(int, input().split()):
    if x >= 0: heapq.heappush(positive, x)
    else: heapq.heappush(negative, x)
for _ in range(k):
    if negative:
        heapq.heappush(positive, -heapq.heappop(negative))
    elif positive:
        heapq.heappush(negative, -heapq.heappop(positive))
print(sum(positive) + sum(negative))

C++ 程式碼

使用時間約為 4 ms，記憶體約為 408 kB，通過測試。

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

int main() {
    int n, k; scanf("%d %d", &n, &k);
    priority_queue<int, vector<int>, greater<int>> positive, negative;
    for(int i=0, x; i<n; i++) {
        scanf("%d", &x);
        if (x >= 0) positive.push(x);
        else negative.push(x);
    }
    for(int i=0, x; i<k; i++) {
        if (!negative.empty()) {
            x = negative.top();
            negative.pop();
            positive.push(-x);
        } else if (!positive.empty()) {
            x = positive.top();
            positive.pop();
            negative.push(-x);
        }
    }
    int isum = 0;
    while(!positive.empty()) {
        isum += positive.top();
        positive.pop();
    }
    while(!negative.empty()) {
        isum += negative.top();
        negative.pop();
    }
    printf("%d\n", isum);
    return 0;
}