#T273. 最大值的位置
最大值的位置
给定一个 行 列的整数矩阵,请找出矩阵中的最大值,并输出这个值以及它第一次出现的位置。
矩阵的行从上到下依次编号为 ,列从左到右依次编号为 。本题所说的位置一律用行号和列号描述,且两者都从 开始。
最大值可能在矩阵中出现多次。此时规定:位置按行优先顺序比较,先比行号,行号小的更靠前;行号相同时再比列号,列号小的更靠前。也就是说,从第 行开始逐行向下扫描,每行内从左到右扫描,第一次遇到最大值的位置就是答案位置。等价地说,所有达到最大值的格子中,取行号最小的;若有多个格子的行号都最小,再取其中列号最小的。
输入格式
第一行两个整数 ()和 (),分别表示矩阵的行数与列数,两个整数之间用一个空格分隔。
接下来 行,每行 个整数,同一行内相邻整数之间用一个空格分隔,行末没有多余空格。第 行第 个整数为 (),表示矩阵第 行第 列的元素。
输出格式
输出一行三个整数,相邻两个整数之间用一个空格分隔,行末输出换行符。三个整数依次是:
- 矩阵所有元素中的最大值;
- 该最大值第一次出现时所在的行号;
- 该最大值第一次出现时所在的列号。
因为行优先规则唯一确定了位置,本题的正确答案完全唯一。不要输出其他内容。
数据范围
- ,,矩阵最多有 个元素。
- 对每个 与 ,都有 。
- 元素可以是负数、零,也可以重复出现;同一个值可能出现多次。
样例
3 4
1 7 3 7
5 2 7 4
6 0 7 1
7 1 2
最大值为 ,它在矩阵中出现了 次,位置分别是第 行第 列、第 行第 列、第 行第 列、第 行第 列。其中行号最小的是第 行,第 行里列号最小的是第 列,所以第一次出现的位置是第 行第 列。
2 3
-5 -1 -9
-1 -7 -3
-1 1 2
所有元素都是负数,最大值为 。它出现在第 行第 列和第 行第 列,两处行号不同,行号小的更靠前,因此输出第 行第 列。注意这里不能按列号优先比较:第 行第 列的列号更小,但它不是行优先顺序下的第一次出现。
1 1
-1000000000
-1000000000 1 1
矩阵只有一个元素,此时它既是最大值,也是唯一的出现位置,行号和列号都是 。
说明
- 输出中的行号、列号都是题目中的 起始编号。若在 C++ 里用从 开始的下标记录位置,输出前需要各自加 。
- 最大值本身可能是负数,所以不能用「初始最大值取 」的写法。
- 本题时限 1000 ms,内存 256 MiB。
相关
在下列比赛中: