APCS 實作題 10510 第2題最大和參考解法

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

此題在高中生程式解題系統的題號為：https://zerojudge.tw/ShowProblem?problemid=c295。

解法一，排序為主：

  1. 用二維整數陣列(也就是矩陣) d[20][20] 來存放資料。
  2. 針對矩陣的每一列(也就是每一群數字)作由小到大排序，而第 i 群數字的最大值會在 d[i][m-1] 位置上。
  3. 將每一群的最大數字做加總，儲存在整數變數 sum。
  4. 判斷每一群的所挑選出來的數字是否整除 sum。
  5. 使用 flag 來判斷這 n 群是否有一群以上的數字可整除 sum。


C++ 程式碼：
 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
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    int d[20][20] = {0};    // 用二維整數陣列(也就是矩陣) d[20][20] 來存放資料。
    int n, m;

    while(cin >> n >> m)    // 讀取 n, m
    {
        // 讀取每一群的數字
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                cin >> d[i][j];

        // 針對矩陣的每一列(也就是每一群數字)作由小到大排序
        for(int i = 0; i < n; i++)
            sort(d[i], d[i] + m);

        // 將每一群的最大數字做加總，儲存在整數變數 sum。
        int sum = 0;
        for(int i = 0; i < n; i++)
            sum = sum + d[i][m-1];  // 第 i 群數字的最大值會在 d[i][m-1] 位置上。

        cout << sum << endl;

        int flag = 0;   // 判斷這 n 群是否有一群以上的數字可整除 sum。

        // 判斷每一群的所挑選出來的數字是否整除 sum。
        for(int i = 0; i < n; i++)
        {
            int v = d[i][m-1];
            if(sum % v == 0)    // 第 i 群所挑出來的數字是否有整除sum。
            {
                if(flag == 0)   // 可整除的第一個數字不用空白
                    cout << v;
                else
                    cout << " " << v;   // 可整除的第二個數字，前面需要加上空白

                flag = 1;
            }
        }

        // 判斷這 n 群是否有一群以上的數字可整除 sum。
        if(flag == 0)
            cout << -1 << endl;

    }

    return 0;
}

C 程式碼：
 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
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b)
{
    return ( *(int*)a - *(int*)b );
}

int main(void) {
    int d[20][20] = {0};    // 用二維整數陣列(也就是矩陣) d[20][20] 來存放資料。
    int n, m;

    while(scanf("%d%d", &n, &m) == 2)    // 讀取 n, m
    {
        // 讀取每一群的數字
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                scanf("%d", &d[i][j]);

        // 針對矩陣的每一列(也就是每一群數字)作由小到大排序
        for(int i = 0; i < n; i++)
            qsort(d[i], m, sizeof(int), cmp);

        // 將每一群的最大數字做加總，儲存在整數變數 sum。
        int sum = 0;
        for(int i = 0; i < n; i++)
            sum = sum + d[i][m-1];  // 第 i 群數字的最大值會在 d[i][m-1] 位置上。

        printf("%d\n", sum);

        int flag = 0;   // 判斷這 n 群是否有一群以上的數字可整除 sum。

        // 判斷每一群的所挑選出來的數字是否整除 sum。
        for(int i = 0; i < n; i++)
        {
            int v = d[i][m-1];
            if(sum % v == 0)    // 第 i 群所挑出來的數字是否有整除sum。
            {
                if(flag == 0)   // 可整除的第一個數字不用空白
                    printf("%d", v);
                else
                    printf(" %d", v);   // 可整除的第二個數字，前面需要加上空白

                flag = 1;
            }
        }

        // 判斷這 n 群是否有一群以上的數字可整除 sum。
        if(flag == 0)
            printf("-1\n");

    }

    return 0;
}

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
30
31
32
while True:
    try:
        n, m = map(int, input().split())

        m = []
        for i in range(n):
            v = list(map(int, input().split()))
            v.sort(reverse = True)  # 由大到小做排序
            m.append(v)

        # 算總和
        sum = 0
        for v in m:
            sum = sum + v[0]
        
        print(sum)

        flag = 0
        for v in m:
            i = v[0]
            if sum % i == 0:    # 此群最大值是否可以整除總和
                if flag == 0:
                    print(i, end='')
                else:
                    print('', i, end='')
                flag = 1

        if flag == 0:
            print(-1)

    except EOFError:
        break

解法二，不排序：

  1. 用一個整數陣列 v[20] 來存放每群數字的最大值。
  2. 每一群資料在讀取時，邊判斷目前讀取到的數字是不是最大值。
  3. 讀完一群數字後，將此群的最大值存放到 v[i] 中，並加總到 sum 。 
  4. 判斷每一群的所挑選出來的數字是否整除 sum。
  5. 使用 flag 來判斷這 n 群是否有一群以上的數字可整除 sum。


C++ 程式碼：
 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
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>

using namespace std;

int main(void) {
    int v[20];  // 用一維陣列來儲存每一群的最大值
    int n, m;

    while(cin >> n >> m)    // 讀取 n, m
    {
        int sum = 0;

        // 讀取每一群的數字
        for(int i = 0; i < n; i++)
        {
            int x = 0;  // 此群的最大值
            for(int j = 0; j < m; j++)
            {
                int t;
                cin >> t;
                if(x < t) x = t;
            }
            v[i] = x;       // 儲存此群的最大值
            sum += x;       // 將每一群的最大數字做加總。
        }

        cout << sum << endl;

        int flag = 0;   // 判斷這 n 群是否有一群以上的數字可整除 sum。

        // 判斷每一群的所挑選出來的數字是否整除 sum。
        for(int i = 0; i < n; i++)
        {
            int x = v[i];
            if(sum % x == 0)    // 第 i 群所挑出來的數字是否有整除sum。
            {
                if(flag == 0)   // 可整除的第一個數字不用空白
                    cout << x;
                else
                    cout << " " << x;   // 可整除的第二個數字，前面需要加上空白

                flag = 1;
            }
        }

        // 判斷這 n 群是否有一群以上的數字可整除 sum。
        if(flag == 0)
            cout << -1 << endl;

    }

    return 0;
}

C 程式碼：
 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
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int v[20];
    int n, m;

    while(scanf("%d%d", &n, &m) == 2)    // 讀取 n, m
    {
        int sum = 0;

        // 讀取每一群的數字
        for(int i = 0; i < n; i++)
        {
            int x = 0;  // 此群的最大值
            for(int j = 0; j < m; j++)
            {
                int t;
                scanf("%d", &t);
                if(x < t) x = t;
            }
            v[i] = x;       // 儲存此群的最大值
            sum += x;       // 將每一群的最大數字做加總。
        }

        printf("%d\n", sum);

        int flag = 0;   // 判斷這 n 群是否有一群以上的數字可整除 sum。

        // 判斷每一群的所挑選出來的數字是否整除 sum。
        for(int i = 0; i < n; i++)
        {
            int x = v[i];
            if(sum % x == 0)    // 第 i 群所挑出來的數字是否有整除sum。
            {
                if(flag == 0)   // 可整除的第一個數字不用空白
                    printf("%d", x);
                else
                    printf(" %d", x);   // 可整除的第二個數字，前面需要加上空白

                flag = 1;
            }
        }

        // 判斷這 n 群是否有一群以上的數字可整除 sum。
        if(flag == 0)
            printf("-1\n");

    }

    return 0;
}

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
while True:
    try:
        n, m = map(int, input().split())
        sum = 0
        m = []
        for i in range(n):
            v = max(list(map(int, input().split())))    # 找這一群數字的最大值
            sum = sum + v                               # 每一群的最大值做加總
            m.append(v)                                 # 將每一群的最大值存到 m

        print(sum)
        flag = 0
        for i in m:
            if sum % i == 0:    # 此群最大值是否可以整除總和
                if flag == 0:
                    print(i, end='')
                else:
                    print('', i, end='')
                flag = 1

        if flag == 0:
            print(-1)

    except EOFError:
        break

Labels: , , ,