ZeroJudge E559: Luggage

同題:UVa 10664 – Luggage

Peter 和他的朋友們正在度假,他們決定乘車去西班牙的北部。
他們總共七個人,他們認為兩輛汽車足以容納所有人的行李。
時間到啦!該出發了。
司機們對哪個行李箱必須放入哪個後車箱持不同意見,因為沒人希望自己的車載的行李更重(因為耗油)。
要如何才能讓兩輛汽車載的行李重量相同?(司機不能把行李拆開或者分裝!)
考慮每個行李箱外都有一個標籤 M 代表該行李重量。
如果可能的話,請你幫個忙,讓兩輛汽車載的行李重量相同。

範例測資

範例輸入範例輸出
輸入的第一行包含一個整數 T,T 代表測資數量。
每組測資一行,此行包含 N 個整數 (1 ≤ N ≤ 20)。
這些整數代表每個行李箱的重量 M (0 < M ≤ 200)。
對於每組測資,如果可以讓兩輛汽車載的行李重量相同,輸出「YES」。否則輸出「NO」。
3
1 2 1 2 1
2 3 4 1 2 5 10 50 3 50
3 5 2 7 1 7 5 2 8 9 1 25 15 8 3 1 38 45 8 1
NO
YES
YES

解題思路

使用字串收資料,將其切成整數陣列,並且將所有行李的重量加起來,如果所有重量的和為奇數則直接輸出「NO」。反之,計算重量的一半,這個是我們要求的數字,因為只要可以求到一個另外一邊一定也能求到相同的數字。

宣告一個 Map 來存哪些數字或是數字和出現過,將陣列中的數字一一跑過,裡面在跑一個迴圈從一半跑到目前的數字,是 –。如果 Map[目前數字 – 陣列數字] > 0,則將 Map[目前數字]++。最後也要將 Map[陣列數字]++。

如果 Map[一半] > 0,就代表可以平分,反之就是不行。

範例程式碼-ZeroJudge E559: Luggage

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    cin.ignore();
    for (int i = 0; i<T; i++) {
        string str;
        getline(cin, str);
        string add = "";
        vector<int>v;
        int sum = 0;

        for (int j = 0; j<str.length(); j++) {
            const char ch = str[j];
            if (ch == ' ') {
                int toInt;
                if (add.length() == 1) toInt = add[0] - '0';
                else toInt = stoi(add);
                sum += toInt;
                v.push_back(toInt);
                add = "";
                continue;
            }
            add += ch;
        }
        if (add.length() > 0) {
            int tmp;
            if (add.length() == 1) tmp = add[0] - '0';
            else tmp = stoi(add);
            sum += tmp;
            v.push_back(tmp);
        }
        if (sum % 2 != 0) cout << "NO\n";
        else {
            const int half = sum / 2;
            unordered_map<int, int>MAP;
            for (int i = 0; i<v.size(); i++) {
                const int tmp = v[i];
                for (int j = half; j>=tmp; j--) {
                    if (MAP[j-tmp] > 0) MAP[j]++;
                }
                MAP[tmp]++;
            }
            if (MAP[half] > 0) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

//ZeroJudge E559
//Dr. SeanXD

發佈留言