您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

ZOJ 2968 Difference Game 解題詳解：排序與貪心策略求解最大差值

編輯：C++ 入門

題目背景與核心思路

ZOJ 2968 "Difference Game" 是一道經典的算法競賽題目，核心在於從兩個數組中選擇元素構成新數組，使得特定條件下的差值最大化。題目要求在給定操作成本限制 c 下，通過交換兩個數組 ga 和 gb 的元素，使得最終 ga 的最小值與 gb 的最大值之差最大。

算法分析：正數解與負數解的分治策略

情況一：答案為正數

當存在可行解使得差值為正時，問題相對簡單。首先將所有元素合併並升序排序。由於 ga 的最小值必須大於 gb 的最大值，排序後的分割點必然出現在相鄰位置。我們只需從左到右枚舉分割點：左側作為 gb，右側作為 ga，模擬原始數組的交換操作，計算所需成本是否超過 c。若成本在限制內，則記錄當前差值作為候選答案。

情況二：答案為負數

若無法構造正數解，則答案必為負數。此時每次交換一對元素成本為 2，且最終允許一次額外交換（成本為 0 時）。策略簡化為：逐對交換後，考慮最後一個交換位置的兩種情況（即 ga 最小值下移或 gb 最大值上移），取較大者。奇偶數組大小處理邏輯一致。

優化細節與代碼實現

在尋找正數解階段，利用 ga 有序特性可二分查找分割點，但鑑於數據規模較小，代碼採用線性遍歷以簡化實現。完整 C++ 代碼包含輸入處理、排序、solve1 函數枚舉分割點計算成本、以及負數情況的兜底邏輯。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <stack>
#include <algorithm>
using namespace std;

int ga[20005], gb[20005], gc[50000];
int s, c;
int Max = -50006;
int flag = 0;

void solve1() {
    int i, j, k;
    for (i = 1; i < 2 * s; i++) {
        int sum1 = 0, sum2 = 0;
        for (j = s - 1; j >= 0; j--) {
            if (gc[i] > ga[j]) break;
            else sum1++;
        }
        for (k = 0; k <= s - 1; k++) {
            if (gc[i] <= gb[k]) break;
            else sum2++;
        }
        int ka = s - sum1, kb = s - sum2;
        int temp = min(ka, kb);
        int cost = temp * 2;
        int k_diff = abs(ka - kb);
        cost += k_diff * (k_diff - 1);
        if (cost <= c) {
            flag = 1;
            Max = max(Max, gc[i] - gc[i - 1]);
        }
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int i;
        scanf("%d%d", &s, &c);
        for (i = 0; i < s; i++) {
            scanf("%d", &ga[i]);
            gc[i] = ga[i];
        }
        for (i = 0; i < s; i++) {
            scanf("%d", &gb[i]);
            gc[i + s] = gb[i];
        }
        if (s == 1) {
            printf("%d\n", ga[0] - gb[0]);
            continue;
        }
        sort(ga, ga + s);
        sort(gb, gb + s);
        sort(gc, gc + 2 * s);
        flag = 0;
        Max = -50006;
        solve1();
        if (flag == 1) printf("%d\n", Max);
        else {
            Max = max(Max, ga[c / 2 + 1] - gb[s - c / 2 - 1]);
            Max = max(Max, ga[c / 2] - gb[s - c / 2 - 2]);
            printf("%d\n", Max);
        }
    }
    return 0;
}