算法題：排序配對最小化差值和 — 貪心策略證明與實現

題目重述

n 個分數，排序後兩兩配對（最大配最小、次大配次小…），求所有配對差值之和。

貪心證明

設排序後數組 a[0] ≤ a[1] ≤ ... ≤ a[n-1]。
最優配對為 (a[0], a[n-1]), (a[1], a[n-2]), ...。
證明：交換任意兩對中的元素，差值和不減（交換論證）。

代碼實現

#include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int main() {
    int n;
    scanf("%d", &n);
    int* a = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    qsort(a, n, sizeof(int), cmp);

    long long sum = 0;
    for (int i = 0; i < n / 2; i++) {
        sum += a[n - 1 - i] - a[i];
    }
    printf("%lld\n", sum);
    free(a);
    return 0;
}

測試樣例

輸入:
6
100 97 86 59 71 81

排序: 59 71 81 86 97 100
配對: (59,100)=41, (71,97)=26, (81,86)=5
輸出: 72  ✓

複雜度

• 時間：O(n log n) — 排序主導。
• 空間：O(n) — 存儲數組。

變體：分數浮動/權重

若每個分數有權重 w[i]，目標變為 Σ w[i]*|pair_diff|，需動態規劃或最小費用流，不再適用簡單貪心。