HDU 1280 前 M 大的數：計數排序優化兩兩求和 Top-M

題目大意

給定 N 個整數（值 ≤ 5000），兩兩求和（N*(N-1)/2 個和），由大到小輸出前 M 個。

關鍵觀察：值域極小

整數 ≤ 5000 → 和 ≤ 10000。可用 計數排序（Counting Sort） 統計每個和出現次數，避免 O(N^2 log N) 排序。

演算法流程

1. 讀入陣列 arr。
2. 雙層迴圈 i < j 計算和 s = arr[i] + arr[j]，sum[s]++。
3. 從 10000 遞減掃描 sum[]，輸出前 M 個非零計數對應的和值。

代碼實現 (C++)

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAXN = 3005;
int arr[MAXN], sum[10001];

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        for (int i = 0; i < n; ++i) scanf("%d", &arr[i]);
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < n-1; ++i)
            for (int j = i+1; j < n; ++j)
                ++sum[arr[i] + arr[j]];
        
        int cnt = 0;
        for (int v = 10000; v >= 0; --v) {
            while (sum[v]-- > 0) {
                if (cnt++) printf(" ");
                printf("%d", v);
                if (cnt == m) break;
            }
            if (cnt == m) break;
        }
        printf("\n");
    }
    return 0;
}

複雜度分析

• 時間：O(N^2 + V)，V=10001 為值域。N=3000 時 N^2 ≈ 9e6 可接受。
• 空間：O(V)，極小。

總結

善用題目隱含條件（數值範圍小）選擇計數排序/桶排序，是競程優化常用技巧。將「比較排序」降維為「統計頻率」，大幅降低複雜度。