Solution Idea

50042. Highest Mountain

參考解答

此題只需要每個列的最大、第二大數值及行位置和全部中最大數值的位置,故我們每次讀入一個數值時,與目前的最大、次大數值做比較,如果較大,則只需要覆蓋變數即可。

以下為完整程式碼:
ax, ay, av 為全部中最大數值的行、列、值。
pc, qc 為每列中最大及次大的行位置。
pv, qv 為每列中最大及次大的數值。

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
#include <stdio.h>
#include <limits.h>
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int ax, ay, av;
    av = INT_MIN;
    for (int i = 0; i < n; i++) {
        int pc, qc, pv, qv;
        int x;
        pv = qv = INT_MIN;
        for (int j = 0; j < m; j++) {
            scanf("%d", &x);
            if (x >= pv) {
                qv = pv, qc = pc;
                pv = x, pc = j;
            } else if (x >= qv) {
                qv = x, qc = j;
            }
        }
        printf("%d %d\n", pc+1, qc+1);
        if (pv >= av)
            av = pv, ax = i, ay = pc;
    }
    printf("%d %d\n", ax+1, ay+1);
    return 0;
}

注意事項

  1. 若宣告二維陣列儲存全部輸入會造成記憶體超出限制(1MB)。
    4byte(1 integer)*2000000 > 1MB
  2. 因題目要求在相同數值的最大數中,答案為列、行數值中較大者,故判斷不等式需使用 >=
  3. 若讀入數值大於現存最大數值,要覆蓋pv&pc時,需注意第二大數值qv&qc的傳遞覆蓋,否則將出現錯誤答案。

Discussion