Find the Kth Smallest Sum of a Matrix With Sorted Rows trong C++

Cho ma trận m x n các hàng đã sắp xếp, chọn đúng 1 phần tử từ mỗi hàng tạo mảng. Tìm tổng nhỏ nhất thứ k trong tất cả các mảng có thể.

Ví dụ: mat = [[1,3,11],[2,4,6]], k=5 → các tổng nhỏ nhất: [1,2]=3, [1,4]=5, [3,2]=5, [3,4]=7, [1,6]=7 → kết quả 7.

Giải thuật (Priority Queue + Trạng thái)

Mỗi trạng thái = vector chỉ số cột chọn từ mỗi hàng. Dùng min-heap (priority queue) lưu (sum, indices). Mở rộng trạng thái bằng cách tăng chỉ số một hàng.

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;

struct Cmp {
    bool operator()(vector<int>& a, vector<int>& b) {
        return a[0] > b[0]; // min-heap theo sum
    }
};

class Solution {
    priority_queue<vector<int>, vector<vector<int>>, Cmp> pq;
    vector<vector<int>> m;
    int z; // số cột
    
    void update(vector<int>& v, int i, bool ok = false) {
        if (i == v.size()) {
            if (!ok) return;
            int sum = 0;
            for (int j = 0; j < v.size(); j++) sum += m[j][v[j]];
            vector<int> temp = v;
            temp.insert(temp.begin(), sum);
            pq.push(temp);
            return;
        }
        v[i]++;
        if (!ok && v[i] < z) update(v, i + 1, true);
        v[i]--;
        update(v, i + 1, ok);
    }
    
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        m = mat;
        int n = m.size();
        z = m[0].size();
        
        int sum = 0;
        for (int i = 0; i < n; i++) sum += m[i][0];
        
        vector<int> start(n, 0);
        start.insert(start.begin(), sum);
        pq.push(start);
        
        set<vector<int>> visited;
        
        while (k--) {
            auto cur = pq.top(); pq.pop();
            if (visited.count(cur)) { k++; continue; }
            visited.insert(cur);
            int curSum = cur[0];
            cur.erase(cur.begin());
            update(cur, 0);
            if (k == 0) return curSum;
        }
        return 0;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,3,11},{2,4,6}};
    cout << ob.kthSmallest(v, 5); // 7
    return 0;
}

Đầu vào / Đầu ra

Input: {{1,3,11},{2,4,6}}, k=5
Output: 7