计算鞍点

题目描述

输入格式：一个 $5 \times 5$ 的整数矩阵，共 5 行 5 列，且每行只有一个最大值、每列只有一个最小值。

输出格式：求鞍点——它既是所在行的最大值、又是所在列的最小值；存在则输出行号、列号和值，不存在则输出 not found。样例输入为 11 3 5 6 9 / 12 4 7 8 10 / 10 5 6 9 11 / 8 6 4 7 2 / 15 10 11 20 25 五行，样例输出为 4 1 8（第 4 行第 1 列的 8）。

思路

鞍点必然是所在行的最大值，而每行最大值唯一，所以每行只有一个候选位置，不必检查全部 25 个格子。先预处理出每列的最小值，再逐行找出最大值的列号，验证该值是否等于对应列最小值，复杂度 $O(5 \times 5)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com  github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 19:50
# update_at: 2026-09-29 19:50

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    a = [[next(data) for _ in range(5)] for _ in range(5)]      # 逐行顺序消费 5x5

    col_min = [min(col) for col in zip(*a)]                      # 每列的最小值

    # 鞍点：行最大值位置恰好也是该列最小值；矩阵保证唯一，next 找不到给默认值
    ans = next(
        ((i + 1, j + 1, row[j])
         for i, row in enumerate(a)                                # 逐行找最大值所在列 j
         for j in [max(range(5), key=lambda j: row[j])]
         if row[j] == col_min[j]),
        None)

    print('not found' if ans is None else '{} {} {}'.format(*ans))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 02:31
 * update_at: 2026-10-05 02:31
 */
#include <cstdio>

typedef long long ll; // 题目数据统一用 long long

const int N = 5; // 矩阵固定 5 行 5 列

ll a[N + 1][N + 1];    // a[i][j] 表示第 i 行第 j 列的元素，行列均从 1 编号
ll col_min[N + 1];     // col_min[j] 表示第 j 列的最小值（题目保证每列唯一）

int main() {
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            scanf("%lld", &a[i][j]);

    // 预处理每列最小值，之后验证"列最小"只需一次比较
    for (int j = 1; j <= N; ++j) {
        col_min[j] = a[1][j];
        for (int i = 2; i <= N; ++i)
            if (a[i][j] < col_min[j]) col_min[j] = a[i][j];
    }

    // 鞍点必然是该行最大值；每行最大值唯一，逐行取一个候选再验证列最小性
    for (int i = 1; i <= N; ++i) {
        int max_col = 1; // 本行最大值的列号
        for (int j = 2; j <= N; ++j)
            if (a[i][j] > a[i][max_col]) max_col = j;
        if (a[i][max_col] == col_min[max_col]) {
            printf("%d %d %lld\n", i, max_col, a[i][max_col]);
            return 0;
        }
    }

    printf("not found\n");
    return 0;
}

目录

题目描述

思路

参考代码