7 矩阵中战斗力最弱的 K 行

7 矩阵中战斗力最弱的 K 行

作者: Turbo时间限制: 1S章节: 课程设计

问题描述 :

给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。

请你返回矩阵中战斗力最弱的 k 行的索引（行号），按从最弱到最强排序。

如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。

军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。

示例 1：

输入：

5 5

1 1 0 0 0 

1 1 1 1 0 

1 0 0 0 0 

1 1 0 0 0 

1 1 1 1 1

3

输出：

2 0 3

解释：

每行中的军人数目：

行 0 有 2 人

行 1 有 4 人

行 2 有 1 人

行 3 有 2 人

行 4 有 5 人

从最弱到最强对这些行排序后得到 [2,0,3,1,4]

示例 2：

输入：

4 4

1 0 0 0 

1 1 1 1 

1 0 0 0 

1 0 0 0

2

输出：

0 2

解释： 

每行中的军人数目：

行 0 有 1 人

行 1 有 4 人

行 2 有 1 人

行 3 有 1 人

从最弱到最强对这些行排序后得到 [0,2,3,1]

输入说明 :

输入若干行：

第一行输入两个整数m和n，表示矩阵的行数和列数。

之后m行，每行输入n个整数（0或1）表示矩阵的元素。

最后一行输入一个整数k(1 <= k <= m).

提示：

    2 <= n, m <= 100

    1 <= k <= m

    矩阵的元素 不是 0 就是 1

输出说明 :

输出一行k个整数，每个整数后跟一个空格。

输入范例 :

4 4
1 0 0 0
1 1 0 0
1 0 0 0
1 1 1 0
3 

输出范例 :

0 2 1 

#include<iostream>
#include<algorithm>
using namespace std;
 
struct student
{
	
		int line= -1;
		int number= 0;
 
};
bool cmp(student x, student y)
{
	if (x.number == y.number)
		return x.line < y.line;
	else
		return x.number < y.number;
}
int main()
{
	int arr[500][500];
	student m[100];
	int x = 0; 
	int y = 0;
	cin >> x >> y;
 
	for (int i = 0; i < x; i++)
	{
		m[i].line = i;		
		for (int u = 0; u < y; u++)
		{
			cin >> arr[x][u];
			if (arr[x][u] == 1)
			{
				m[i].number++;
			}
		}
	}
 
	int k = 0;
	cin >> k;
	sort(m, m + x, cmp);
	for (int i = 0; i < k; i++)
	{
		cout << m[i].line;
 
			cout << " ";
	}
 
	return 0;
}