个人任务7.矩阵中战斗力最弱的 K 行

╰半橙微兮° 2023-09-28 13:18 24阅读 0赞

作者: 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<vector>
    #include<string>
    #include<sstream>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<stdlib.h>
    #include<stdio.h>
    #include<fstream>
    #include<iomanip>
    #include<utility>
    using namespace std;
    int a[101]={
        0};//a数组用来记录一行中军人的数量
    int b[101][101]={
        0};
    
    bool cmp(pair<int,int> we,pair<int,int> wk){
        
        return we.second<wk.second;//根据second的值升序排列
    }
    
    int main(){
        
        int n,m,k;//k表示要输出排序数组的最弱的前几行
        cin>>n>>m;
        for(int i=0;i<n;++i){
        
            for(int j=0;j<m;++j){
        
                cin>>b[i][j];//输入n行m列的二维数组
                if(b[i][j]==1)
                    a[i]++;//在输入的过程中就计数
            }
        }
        cin>>k;
        pair<int,int> dui[n];
        for(int i=0;i<n;++i)
            dui[i]=make_pair(i,a[i]);//将对应序号和军人个数形成对组
        stable_sort(dui,dui+n,cmp);
        for(int i=0;i<k;++i)
            cout<<dui[i].first<<" ";
        return 0;
    }