題目： UVa - 978 - Lemmings Battle!

題目說明

有兩個隊伍需要戰鬥，每個隊伍裡面的戰士都有一個戰力，每次從隊伍裡面挑選 B 個人 ( 若任一隊伍不足 B 個人則以較少隊伍的人數當作 B ) 出來依序戰鬥，若是被分配到的兩者戰力相等則同歸於盡，否則戰力較高的戰士減去戰力較低的戰士的戰力並回到隊伍中。

Input： 測資起始於一個整數 n，代表接下來會有 n 組資料。每組資料的第一行為三個整數，分別代表 B、SG、SB，SG 為綠隊的人數，SB 為藍隊的人數，三者以空格隔開，接下來 SG 行為綠隊戰士的戰力，SB 行為藍隊戰士的戰力。

Output： 若兩支隊伍最後都沒有戰士了則輸出 "green and blue died"，否則輸出勝利的隊伍，並且列出勝利隊伍剩餘戰士的戰力，並由大至小排序。兩組輸出結果中間須以空行隔開。

解題思路

使用兩個 Priority_queue 分別儲存兩隊戰士的戰力，並且每次 pop() 對應的人數戰鬥，使用 Vector 暫存戰鬥結果，最後依照戰鬥的結果將戰士重新 push() 回去即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

int main()
{
    int n;
    cin >> n;
    
    while (n--)
    {
        int b, sg, sb, tmp;
        cin >> b >> sg >> sb;

        priority_queue<int> G, B;

        while (sg--) cin >> tmp, G.push(tmp);
        while (sb--) cin >> tmp, B.push(tmp);

        while (!G.empty() && !B.empty())
        {
            vector<int> battle;
            for (int i = 0; i < b; ++i)
            {
                if (G.empty() || B.empty()) break;
                battle.push_back(G.top() - B.top());
                G.pop(), B.pop();
            }
            for (auto& ret : battle)
            {
                if (ret > 0) G.push(ret);
                else if (ret < 0) B.push(-ret);
            }
        }

        if (G.empty() && B.empty()) cout << "green and blue died\n";
        else
        {
            if (!G.empty())
            {
                cout << "green wins\n";
                while (!G.empty()) cout << G.top() << '\n', G.pop();
            }
            else
            {
                cout << "blue wins\n";
                while (!B.empty()) cout << B.top() << '\n', B.pop();
            }
        }

        if (n) cout << '\n';
    }
}