逐行找唯一最大值，再判断它是否同时为所在列最小值来定位鞍点。
OJ: noi_openjudge
题目 ID: ch0108-05
难度:入门
标签:矩阵模拟python
日期: 2026-07-30 23:01
题意
寻找
思路
每行最多只有一个候选，即该行最大值。找到候选列后，检查它是否等于这一列的最小值；满足时立即输出。
代码
cpp
#include <cstdio>
int a[10][10];
int main(){
int i,j;
for (i=1;i<=5;i++){
for (j=1;j<=5;j++){
scanf("%d",&a[i][j]);
}
}
for (i=1;i<=5;i++){
int max = -1;
int pos;
for (j=1;j<=5;j++){
if( a[i][j] > max ){
max = a[i][j];
pos = j;
}
}
bool flag = true;
for(j=1;j<=5;j++){
if(a[j][pos] < max){
flag = false;
break;
}
}
if( flag == true){
printf("%d %d %d",i,pos,max);
return 0;
}
}
printf("not found");
return 0;
}复杂度
总结
Python代码
python
matrix = [list(map(int, input().split())) for _ in range(5)]
for row, values in enumerate(matrix):
value = max(values)
column = values.index(value)
if value == min(matrix[index][column] for index in range(5)):
print(row + 1, column + 1, value)
break
else:
print("not found")C++代码
cpp
#include <cstdio>
int a[10][10];
int main(){
int i,j;
for (i=1;i<=5;i++){
for (j=1;j<=5;j++){
scanf("%d",&a[i][j]);
}
}
for (i=1;i<=5;i++){
int max = -1;
int pos;
for (j=1;j<=5;j++){
if( a[i][j] > max ){
max = a[i][j];
pos = j;
}
}
bool flag = true;
for(j=1;j<=5;j++){
if(a[j][pos] < max){
flag = false;
break;
}
}
if( flag == true){
printf("%d %d %d",i,pos,max);
return 0;
}
}
printf("not found");
return 0;
}复杂度
矩阵规模固定，时间和额外空间复杂度均为
总结
行最大、列最小的复合条件可先缩小到每行唯一候选，再验证另一条件。