# 題目: UVa 978 - Lemmings Battle

# 題目說明

兩個種族正在進行戰鬥,到底是綠色種族贏還是藍色種族贏呢?
寫一個程式來判斷哪個種族獲得了勝利


INPUT:
第一行有一個整數 N ,代表有幾筆資料
每筆資料第一行有三個整數 BSGSB

  • 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/