同題: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