小雪患了一種奇怪的傳染病，身上長滿了疹子，全身又痛又癢的，就連醫生也查不出病情。正當苦惱之時，有一位神秘婆婆突然出現，說他有一道祖傳的神奇解藥可以治好小雪的病，但是這個解藥需要有四種材料 A、B、C、和 D，且必須要以特殊的比例才能製作。
每種材料婆婆都分装成不同大小份量的 N 小包，且每小包都不能再切分或合併。以下表為例，每種材料都分成五小包，材料 A 五小包的份量為 2、9、5、8、和 1，材料B 五小包的份量為 8、3、1、4、和 5，以此類推。若解藥的最佳比例為 1：2：1：3，我們可對 A 材料拿取第一小包、B 材料拿取第四小包、C 材料拿取第四小包、D 材料拿取第三小包，以按照正確比例製成解藥。
請你撰寫一個程式判斷是否能夠按指定比例製成解藥。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 輸入第一列有四個正整數 A、B、C、D (數值均不大於 5），表示製作解藥的四種材料比例，保證必有一數字為 1。接著第二列有一個整數 N (3 ≤ N ≤ 10），代表四種材料都分成幾包。最後四列，每一列有 N 個整數 X：(1 ≤ X ≤ 100，1 ≤ i ≤ N) 分別代表此材料的每小包份量。 | 輸出一列製作此解藥的每項材料份量，若無法製作解藥則輸出-1，保證答案最多只有一組解。 |
| 1 2 1 3 5 2 9 5 8 1 8 3 1 4 5 1 6 5 2 7 4 3 6 9 8 | 2 4 2 6 |
| 1 2 1 3 3 2 9 5 8 3 1 1 6 5 4 3 1 | -1 |
| 2 2 1 3 7 7 10 8 6 3 2 7 2 7 10 1 2 4 3 4 1 10 5 9 8 6 4 8 2 1 8 3 3 | 2 2 1 3 |
解題思路
可以使用陣列將比例收起來，然後宣告一個 Vector<map<int, int>> 來存每一種藥分別有哪些份量。
跑一個 For迴圈，當現在的藥比例是 1 時，就把這種藥的份量當作是基準，去其他三種藥尋找是否有符合比例的藥物，將答案存在一個陣列中。
範例程式碼－ZeroJudge K514: 解藥 (Medicine)
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int ratio[4] = {}, N;
for (int & i : ratio) cin >> i;
cin >> N;
vector<map<int, int>>v;
for (int i = 0; i<4; i++) {
map<int, int>MAP;
for (int j = 0; j<N; j++) {
int tmp;
cin >> tmp;
MAP[tmp]++;
}
v.push_back(MAP);
}
bool no = true;
for (int i = 0; i<4; i++) {
if (ratio[i] == 1) {
bool finish = false;
for (auto it:v[i]) {
const int num = it.first;
int ans[4] = {};
ans[i] = num;
bool ok = true;
for (int j = 0; j<4; j++) {
if (i == j) continue;
if (v[j][num*ratio[j]] > 0) ans[j] = num*ratio[j];
else {
ok = false;
break;
}
}
if (ok) {
for (int j = 0; j<4; j++) cout << ans[j] << " ";
cout << "\n";
finish = true;
break;
}
}
if (finish) {
no = false;
break;
}
}
}
if (no) cout << -1 << "\n";
}
//ZeroJudge K514
//Dr. SeanXD