題目大意

給定 k 行數據，每行 k 個整數（已排序）。從每行各取一個數，共 k 個數求和。所有可能的 k^k 種組合中，求最小的 k 個和，按升序輸出。

約束：k ≤ 750，暴力枚舉 k^k 不可行。

核心思路：逐行合併 + 最小堆

將問題轉化為：已有前 i 行的最小 k 個和，合併第 i+1 行得到新的最小 k 個和。

1. 初始：第一行本身就是最小 k 個和（已排序）。
2. 合併第 j 行：維護一個最小堆，初始放入 sum[0] + row[j][0]（sum 為前 j-1 行的最小 k 和）。
3. 每次彈出堆頂最小和 s = sum[x] + row[j][y]，輸出/記錄，然後推入 sum[x] + row[j][y+1]（同一行下一個元素）。
4. 重複 k 次得到新的最小 k 個和，作為下一輪的 sum。

關鍵數據結構

struct Elem {
    int sum; // 當前和
    int idx; // 對應 sum 數組的索引 x
    bool operator<(const Elem& other) const { return sum > other.sum; } // 最小堆
};

完整代碼 (C++)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;

const int MAXK = 768;
int a[MAXK][MAXK];
int k;

void mergeRow(int row) {
    priority_queue<Elem> pq;
    int tmp[MAXK];
    
    // 初始化堆：前 k 小和 + 當前行第一個元素
    for (int i = 0; i < k; ++i)
        pq.push({a[0][i] + a[row][0], i});
    
    // 取出 k 個最小和
    for (int i = 0; i < k; ++i) {
        Elem cur = pq.top(); pq.pop();
        tmp[i] = cur.sum;
        int x = cur.idx;
        if (x + 1 < k) // 注意：這裡應推入 sum[x] + row[y+1]，但因 sum 已排序且行已排序，實際邏輯需調整
            pq.push({cur.sum - a[0][x] + a[0][x+1], x+1}); // 修正：推入同行下一個元素組合
            // 正確邏輯：cur.sum = sum[x] + row[y]，下一個應為 sum[x] + row[y+1]
            // 但題目中 row 固定，sum 為前幾行合併結果，需維護 y 索引
    }
    // 複制回 a[0]
    for (int i = 0; i < k; ++i) a[0][i] = tmp[i];
}

// 修正後的標準合併邏輯
void mergeRowCorrect(int row) {
    priority_queue<Elem> pq;
    int tmp[MAXK];
    // Elem 應包含 sum_idx, row_idx
    struct Node { int s, si, ri; bool operator<(Node o) const { return s > o.s; } };
    priority_queue<Node> q;
    for (int i = 0; i < k; ++i)
        q.push({a[0][i] + a[row][0], i, 0});
    for (int i = 0; i < k; ++i) {
        Node cur = q.top(); q.pop();
        tmp[i] = cur.s;
        if (cur.ri + 1 < k)
            q.push({cur.s - a[row][cur.ri] + a[row][cur.ri+1], cur.si, cur.ri+1});
    }
    for (int i = 0; i < k; ++i) a[0][i] = tmp[i];
}

int main() {
    while (scanf("%d", &k) != EOF) {
        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < k; ++j) scanf("%d", &a[i][j]);
            sort(a[i], a[i] + k);
        }
        for (int i = 1; i < k; ++i) mergeRowCorrect(i);
        for (int i = 0; i < k; ++i)
            printf("%d%c", a[0][i], i == k-1 ? '\n' : ' ');
    }
    return 0;
}

複雜度分析

• 排序：k 行 × O(k log k) = O(k² log k)
• 合併：k-1 輪 × k 次堆操作 × O(log k) = O(k² log k)
• 總時間：O(k² log k)，k=750 時約 400萬操作，極快。
• 空間：O(k²) 存儲矩陣 + O(k) 堆。

關鍵點總結

1. 利用行有序特性，將 k 維問題分解為 k-1 次二維合併。
2. 最小堆維護候選和，每次取最小並推入同行下一個元素組合（類似合併 k 個有序鏈表）。
3. STL priority_queue 默認大頂堆，需重載 operator< 反轉或用 greater 實現小頂堆。