Force deduction exercise - the sum of the kth smallest array in the 21 ordered matrix

21 In an ordered matrix k The smallest array and

1. Problem description
To give you one m * n Matrix mat, And an integer k , Every row in the matrix is arranged in a non decreasing order .

You can choose from each line 1 Elements form an array . Returns the second of all possible arrays k individual Minimum Array and .

Example 1：

Input ：mat = [[1,3,11],[2,4,6]], k = 5

Output ：7

explain ： Select an element from each row , front k And the smallest array is ：

[1,2], [1,4], [3,2], [3,4], [1,6]. Among them the first 5 The sum of two is 7 .

Example 2：

Input ：mat = [[1,3,11],[2,4,6]], k = 9

Output ：17

Example 3：

Input ：mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7

Output ：9

explain ： Select an element from each row , front k And the smallest array is ：

[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Among them the first 7 The sum of two is 9 .

Example 4：

Input ：mat = [[1,1,10],[2,2,9]], k = 7

Output ：12

explain ：

m ,n For matrix mat The number of rows and columns of

1 <= m, n <= 40

1 <= k <= min(200, n ^ m)

1 <= mat[i][j] <= 5000

mat[i] It is a group of non decreasing numbers

Refer to the following main function ：

int main()

{

int m, n,data,k;

vector<vector<int> > mat;

cin>>m>>n;

for(int i=0; i<m; i++)

{

    vector<int> row;

    for(int j=0; j<n; j++)

    {

        cin>>data;

        row.push_back(data);

    }

    mat.push_back(row);

}

cin>>k;

int res=Solution().kthSmallest(mat,k);

cout<<res<<endl;

return 0;

}

2. Enter description
First enter the matrix mat The number of rows and columns of m and n

Then input m That's ok , Each row n Nonnegative integers , Express mat The element value of , Space off .

Last input k.
3. The output shows that
Output an integer , Show the result .
4. Example
Input
2 3
1 3 11
2 4 6
5
Output
7
5. Code

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<set>
using namespace std;

int kthSmallest(vector<vector<int> >mat, int k)
{
    
	// Violence solution 
	// Refer to the website https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/solution/find-the-kth-smallest-sum-of-a-matrix-by-ikaruga/
	//1. Calculate the number of rows and columns 
	int m = mat.size();// Row number 
	int n = mat[0].size();// Number of columns 
	
	vector<int>ans(mat[0]);//ans Save the numbers in the first line 

	for (int i = 1; i < m; i++)
	{
    
		multiset<int>st;//multiset It can always ensure that the numbers in the sequence are ordered , And there can be repeated numbers in the sequence .
		for (int x : ans)// stay i=1 when , Take the number in the first row  ;i=2 when , Take the first row and the second row together to get the first K Number of combinations 
		{
    
			for (int y : mat[i]) //i=1 when , Fetching in the second line  etc
			{
    
				st.insert(x + y);//i=1, Add the number combinations of the first and second rows 
			}
		}
		ans.assign(st.begin(), st.end());// Assign the added number to ans, Implement update operation 
		ans.resize(min(k, (int)ans.size()));// Only take the first in the sequence table K It's worth 
	}
	return ans.back();// The final value is the desired number K The smallest array and 
}

 
int main()

{
    

	int m, n, data, k;

	vector<vector<int> > mat;

	cin >> m >> n;

	for (int i = 0; i < m; i++)

	{
    

		vector<int> row;

		for (int j = 0; j < n; j++)

		{
    

			cin >> data;

			row.push_back(data);

		}

		mat.push_back(row);

	}

	cin >> k;

	int res = kthSmallest(mat, k);

	cout << res << endl;

	return 0;

}