# 題目: UVa 978 - Lemmings Battle
# 題目說明
兩個種族正在進行戰鬥,到底是綠色種族贏還是藍色種族贏呢?
寫一個程式來判斷哪個種族獲得了勝利
INPUT:
第一行有一個整數 N
,代表有幾筆資料
每筆資料第一行有三個整數 B
、 SG
和 SB
B
代表每次戰鬥派出的人數SG
代表綠色種族人數SB
代表藍色種族人數
接下來的SG
為綠色種族的戰力,SB
為藍色種族的戰力
OUTPUT:
如果雙方全軍覆沒則輸出 green and blue died
如果一方勝利則輸出勝利種族及存活的戰力 (順序為降冪排序)
# 解題方法
將雙方隊伍存入 multiset
,以 vector
暫存戰鬥結果
每輪戰鬥結束後,將存活的戰力重新由 vector
push 回 multiset
當一方或雙方的 multiset
為空時,判斷勝利種族並輸出
# 參考程式碼
#include <iostream> | |
#include <set> | |
#include <vector> | |
using namespace std; | |
int main() | |
{ | |
ios_base::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
int n, b, sg, sb, temp; | |
multiset<int> green, blue; | |
vector<int> battle; | |
cin >> n; | |
while (n--) { | |
cin >> b >> sg >> sb; | |
while (sg--) cin >> temp, green.emplace(temp); | |
while (sb--) cin >> temp, blue.emplace(temp); | |
while (!green.empty() && !blue.empty()) { | |
for (size_t i = 0; i < b; i++) { | |
if (green.empty() || blue.empty()) break; | |
battle.emplace_back(*green.rbegin() - *blue.rbegin()); | |
auto it = green.end(); | |
green.erase(--it); | |
it = blue.end(); | |
blue.erase(--it); | |
} | |
for (auto& tmp : battle) { | |
if (tmp > 0) green.emplace(tmp); | |
else if (tmp < 0) blue.emplace(-tmp); | |
} | |
battle.clear(); | |
} | |
if (green.empty() && blue.empty()) cout << "green and blue died\n"; | |
else if (green.empty()) { | |
cout << "blue wins\n"; | |
for (auto it = blue.rbegin(); it != blue.rend(); it++) cout << *it << "\n"; | |
blue.clear(); | |
} | |
else { | |
cout << "green wins\n"; | |
for (auto it = green.rbegin(); it != green.rend(); it++) cout << *it << "\n"; | |
green.clear(); | |
} | |
if (n) cout << "\n"; | |
} | |
return 0; | |
} |
# 參考資料
https://www.larrysprognotes.com/UVa%20-%20978/