【題解】ZeroJudge c295: APCS-2016-1029-2最大和

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c295
【Tag】算術運算、條件判斷
【解題想法】

  • 給定N群數字,每群都恰有M個「正整數」。
  • 若從每群數字中各選擇一個數字,計算N個數字的最大總和 (S)。
  • 因為所有數字都是正整數,意即從每群數字中選擇最大的數字。
  • 並判斷各群所選出的數字是否可以整除 S。

【作法-1】array

#include <iostream>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    int sum = 0;
    int a[N];
    for (int i = 0; i < N; i++) {
        int x, mx = 0;
        for (int j = 0; j < M; j++) {
            cin >> x;
            mx = max(mx, x);
        }
        a[i] = mx;
        sum += mx;
    }
    cout << sum << "\n";
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (sum % a[i] == 0) {
            cnt++;
            cout << a[i] << " ";
        }
    }
    if (cnt == 0) {
        cout << "-1\n";
    }
    return 0;
}

【作法-2】vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    int sum = 0;
    vector <int> v(N);
    for (int i = 0; i < N; i++) {
        int x, mx = 0;
        for (int j = 0; j < M; j++) {
            cin >> x;
            mx = max(mx, x);
        }
        v[i] = mx;
        sum += mx;
    }
    cout << sum << "\n";
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (sum % v[i] == 0) {
            cnt++;
            cout << v[i] << " ";
        }
    }
    if (cnt == 0) {
        cout << "-1\n";
    }
    return 0;
}

【作法-3】使用兩個一維vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    int sum = 0;
    vector <int> v(N);
    for (int i = 0; i < N; i++) {
        int x, mx = 0;
        for (int j = 0; j < M; j++) {
            cin >> x;
            mx = max(mx, x);
        }
        v[i] = mx;
        sum += mx;
    }
    cout << sum << "\n";
    vector <int> ans;
    for (int i = 0; i < N; i++) {
        if (sum % v[i] == 0) {
            ans.push_back(v[i]);
        }
    }
    if (ans.size() == 0) {
        cout << "-1\n";
    } else {
        for (auto x : ans) {
            cout << x << " ";
        }
    }
    return 0;
}

【作法-4】使用二維 vector 和 max_element()

但是,這一題,其實不需要把所有input data存下來。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    int sum = 0;
    vector <vector <int>> v(N);
    for (int i = 0; i < N; i++) {
        int x;
        for (int j = 0; j < M; j++) {
            cin >> x;
            v[i].push_back(x);
        }
        sum += *max_element(v[i].begin(), v[i].end());
    }
    cout << sum << "\n";
    vector <int> ans;
    for (int i = 0; i < N; i++) {
        int mx = *max_element(v[i].begin(), v[i].end());
        if (sum % mx == 0) {
            ans.push_back(mx);
        }
    }
    if (ans.size() == 0) {
        cout << "-1\n";
    } else {
        for (auto x : ans) {
            cout << x << " ";
        }
    }
    return 0;
}

Python code

while True:
    try:
        n, m = map(int, input().split())
        lst = []
        total = 0
        for i in range(n):
            templst = list(map(int, input().split()))
            num = max(templst)
            total += num
            lst.append(num)
        print(total)
        anslst = []
        for num in lst:
            if total % num == 0:
                anslst.append(num)  
        if anslst:
            print(' '.join([str(i) for i in anslst]))
        else:
            print(-1)
    except:
        break
分享本文 Share with friends