HNUCM 2022年春季学期《算法分析与设计》练习9斜线最大最小值

题目描述

求如图所示一个上三角矩阵中每一条斜线中的最大元素(L)和最小元素(S)。

输入

每组输入包括两部分，一部分为数字n，表示三角矩阵的行数。
第二部分即为三角矩阵。

输出

每一个对角线输出一行，每行包括Lx=Max, Sx=Min，其中x为斜线序号（序号从1开始），Max为该斜线上的最大值，Min为该斜线上的最小值。

样例输入 Copy

6
1 3 5 7 11 20
0 6 8 2 3 13
0 0 7 4 8 9
0 0 0 18 3 10
0 0 0 0 12 6
0 0 0 0 0 15

样例输出 Copy

L1=18, S1=1
L2=8, S2=3
L3=10, S3=2
L4=9, S4=3
L5=13, S5=11
L6=20, S6=20

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005];bool cmp(int a,int b){//排序return a>b;
}
int main(){int n;while(cin>>n){vector<int>se[1005];//定义一个vector数组for(int i=1;i<=n;i++){int t=0;//注意	for(int j=1;j<=n;j++){cin>>a[i][j];if(a[i][j]!=0){t++;//t最关键，就是判断这个a[i][j]应该放在哪个vector数组里面se[t].push_back(a[i][j]);}}}for(int i=1;i<=n;i++){if(se[i].size()!=1){//遍历，时间复杂度高sort(se[i].begin(),se[i].end(),cmp);cout<<"L"<<i<<"="<<se[i][0]<<", S"<<i<<"="<<se[i][se[i].size()-1]<<endl;}else cout<<"L"<<i<<"="<<se[i][0]<<", S"<<i<<"="<<se[i][0]<<endl;}}return 0;
}

 推荐另一种思路，就是使用set集合，因为他会自动排序，只需要使用iterator遍历到第一个就是最小，最后就是最大