交完这题的感受是，这也能过？难怪这场周赛血崩啊啊啊……

4. 有序矩阵中的第 k 个最小数组和

给你一个 m?* n 的矩阵 mat ，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。
你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。

样例

示例 1：

输入：mat = [[1,3,11],[2,4,6]], k = 5
输出：7
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。

示例 2：

输入：mat = [[1,3,11],[2,4,6]], k = 9
输出：17

示例 3：

输入：mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
输出：9
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。

示例 4：

输入：mat = [[1,1,10],[2,2,9]], k = 7
输出：12

提示

• m == mat.length
• n == mat.length[i]
• 1 <= m, n <= 40
• 1 <= k <= min(200, n ^?m)
• 1 <= mati <= 5000
• mat[i] 是一个非递减数组

思路

看到数据范围，尤其是 k 最大只能是 200 的时候，直接暴力就可以了。
有一点点DP的思想，求完前 i 行的最少 k 个数组和之后，再将这些和与第 i + 1 行的前 k 个数字求和，求得的 k^2 个和，取最小的 k 个供下一行使用。用优先队列维护即可。

代码

写的好丑的喔！！

class Solution {
public:
    int kthSmallest(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        priority_queue<int, vector<int>, greater<int>> que;
        for(int i=0; i<n; i++) que.push(mat[0][i]);
        for(int i=1; i<m; i++) {
            vector<int> pre;
            int cnt = 0;
            for(int j=0; j<k; j++) {
                if(que.empty()) break;
                pre.push_back(que.top());
                que.pop();
                cnt++;
            }
            while(!que.empty()) que.pop();
            for(int j=0; j<n; j++) {
                for(int kk=0; kk<cnt; kk++) {
                    que.push(pre[kk] + mat[i][j]);
                }
            }
        }
        int ans = 0;
        for(int i=0; i<k; i++) {
            ans = que.top();
            que.pop();
        }
        return ans;
    }
};