给你一个 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 ，n为矩阵 mat的行列数
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] 是一个非递减数组
输入说明 :
首先输入矩阵mat的行列数m和n
然后输入m行，每行n个非负整数，表示mat的元素值，以空格分隔。
最后输入k。
输出说明 :
输出一个整数，表示结果。
输入范例 :
2 3
1 3 11
2 4 6
5
输出范例 :
7
1 #include<iostream> 2 #include<map> 3 #include<queue> 4 #include<set> 5 #include<vector> 6 #include<algorithm> 7 using namespace std; 8 class Solution { 9 public: 10 //使用小顶堆 小顶堆中存储每列选的元素的坐标和加和 11 //每次将最小的取出 当第k次取时即为答案 12 //每次取出后 被选的元素的坐标依次加一 13 struct Cell 14 { 15 int sum; 16 vector<int> indexs; 17 Cell(int _sum, vector<int>_v) :sum(_sum), indexs(_v) {}; 18 bool operator <(const Cell& c)const 19 { 20 return sum > c.sum; 21 } 22 }; 23 int kthSmallest(vector<vector<int>>& mat, int k) { 24 priority_queue<Cell> pq; 25 int n = mat.size(), m = mat[0].size(); 26 vector<int> indexs(n, 0); 27 int sum = 0; 28 for (int i = 0; i < n; i++)sum += mat[i][0]; 29 set<vector<int>> indexs_set; 30 indexs_set.insert(indexs); 31 pq.push({ sum, indexs }); 32 while (k--) 33 { 34 Cell c = pq.top(); 35 if (!k)return c.sum; 36 pq.pop(); 37 for (int i = 0; i < n; i++) 38 { 39 indexs.assign( c.indexs.begin(),c.indexs.end()); 40 if (indexs[i] + 1 < m) 41 { 42 indexs[i] += 1; 43 if (indexs_set.find(indexs) == indexs_set.end()) 44 { 45 pq.push({ c.sum - mat[i][indexs[i] - 1] + mat[i][indexs[i]],indexs }); 46 indexs_set.insert(indexs); 47 } 48 } 49 } 50 } 51 return 0; 52 } 53 //动态规划 使用一个数组last_row记录之前所有的行 的最小数组和 54 //然后使用新增加的行的每一个值 都加上last_row的值 然后排序 取前k个 55 //o(n(mk+mklogmk)) 56 /*int kthSmallest(vector<vector<int>>& mat, int k) { 57 vector<int> last_row = { 0 }; 58 vector<int> temp_row; 59 for (int i = 0; i < mat.size(); i++) 60 { 61 // print_v(last_row); 62 for (int j = 0; j < mat[0].size(); j++) 63 { 64 for (int p = 0; p < last_row.size(); p++) 65 { 66 temp_row.push_back(last_row[p] + mat[i][j]); 67 } 68 } 69 sort(temp_row.begin(),temp_row.end()); 70 //print_v(temp_row); 71 if (temp_row.size() > k) 72 last_row.assign(temp_row.begin(), temp_row.begin() + k); 73 else 74 last_row.assign(temp_row.begin(), temp_row.end()); 75 temp_row.resize(0); 76 } 77 return last_row[k - 1]; 78 }*/ 79 }; 80 int main() 81 { 82 int m, n, data, k; 83 vector<vector<int> > mat; 84 cin >> m >> n; 85 for (int i = 0; i < m; i++) 86 { 87 vector<int> row; 88 for (int j = 0; j < n; j++) 89 { 90 cin >> data; 91 row.push_back(data); 92 } 93 mat.push_back(row); 94 } 95 cin >> k; 96 int res = Solution().kthSmallest(mat, k); 97 cout << res << endl; 98 return 0; 99 }