ZeroJudge B116: 加減問題

假設有 N 個正整數 A[1], A[2], …, A[N]，我們要在每一個數字之前加入 + 號或 – 號使得它們的總和為 0。

例如：1、2、3，我們可以得到 (-1) + (-2) + (+3) = 0；但是對於 2、2、1 則無法透過加入 + 號或 – 號使得它們的總和為 0。

請你寫一個程式來判斷任意 N 個正整數是否可以透過加入 + 號或 – 號使得它們的總和為 0。

範例測資

範例輸入範例輸出
輸入檔的第一行有兩個正整數, M及N以空區分，代表有M組。測試資料，每一組有N個正整數。
第二行至第 M+1 行則則分別輸入所訂定的 N 個正整數，以空白區分。其中 0 < M <= 10，且 0 < N <= 100。		對於每一組測試資料，若可以找到加入 + 號或 – 號使得它們的總和為 0 時，請輸出 Yes；否則請輸出 No。
4 3
1 2 3
3 2 1
2 2 2
5 1 6
2 8
1 2 3 4 5 6 7 8
12 12 10 11 34 22 33 26		Yes
Yes
No
Yes
Yes
Yes
ZeroJudge B116 範例測資

解題思路

本題其實就是要找到兩個相同的數字，所以如果總和為奇數，則可以直接輸出「No」。

使用 DFS 的方式把數字進行相加窮舉，如果有出現相加的數字是總和的一半時，代表另外的其他數字相加也會變成總和的一半，所以目的是要找到是否有組合可以加到總合的一半。

範例程式碼－ZeroJudge B116: 加減問題

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

bool ok = false;
int sum = 0;

void DFS(vector<int>num, int index, int count) {
    if (ok || count > sum/2) return;
    if (count == sum/2) {
        ok = true;
        return;
    }
    if (index == num.size()) return;
    for (int i = index; i<num.size(); i++) {
        DFS(num, index+1, count+num[i]);
        if(ok) return;
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int M, N;
    while (cin >> M >> N) {
        for (int i = 0; i<M; i++) {
            vector<int>num;
            int max = -999999;
            sum = 0;
            for (int j = 0; j<N; j++) {
                int tmp;
                cin >> tmp;
                sum += tmp;
                if (tmp > max) max = tmp;
                num.push_back(tmp);
            }
            if (sum/2 < max || sum % 2 == 1) {
                cout << "No\n";
                continue;
            }
            ok = false;
            DFS(num, 0, 0);
            if (ok) {
                cout << "Yes\n";
                continue;
            }
            cout << "No\n";
        }
    }
}

//ZeroJudge B116
//Dr. SeanXD
標籤

相關文章

發佈留言