---
# System prepended metadata

title: UVA 978 - Lemmings Battle!
tags: [林基成-C++, UVA code, cpp, Awwwolf的刷題之路]

---

# UVA 978 - Lemmings Battle!
## Online Judge
![](https://i.imgur.com/tYtRQY0.png)

## 解題思路
由於雙方取出人battle完後，剩下的人還要放回去，最先想到的是用queue，但考慮到要先選最多人的那一組出來這個條件，改成set會比較好，然後multiset才能在容器裡放入相同的元素。
## 解題中出現的bug
1.在雙方人馬battle完後，將活著的人放回去那邊，忘了排除兩方人馬都陣亡的case，造成第一組測資的出現了blue wins 0的好笑output(´･ω･`)
2.output的格式，注意換行。
## Code
```cpp=
#include <iostream>
#include <set>
using namespace std;

int main()
{
    int test_case;
    cin >> test_case;
    while(test_case--)
    {
        multiset<int> q_SG, q_SB;
        int Battle, SG, SB, temp, record_battle[100000]; // temp uses to temp input and it will be put in SG or SB next
        cin >> Battle >> SG >> SB;
        while(SG--)
        {
            cin >> temp;
            q_SG.insert(temp);
        }
        while(SB--)
        {
            cin >> temp;
            q_SB.insert(temp);
        }
        while(!q_SB.empty()&&!q_SG.empty()) // start the fighting!!
        {
            int counter = 0; // record the round of the fight 
            for(int i=0;i<Battle;i++)
            {
                if(q_SB.empty()||q_SG.empty())
                    break;
                record_battle[counter++] = *q_SG.rbegin() - *q_SB.rbegin();
                q_SB.erase(q_SB.lower_bound(*q_SB.rbegin()));
                q_SG.erase(q_SG.lower_bound(*q_SG.rbegin()));
            }
            for(int i=0;i<counter;i++) // put the winner in the fight back to team
            {
                if(record_battle[i]>0)
                    q_SG.insert(record_battle[i]);
                else if(record_battle[i]<0) // Oh... the case of 0 need to be taken off Orz
                    q_SB.insert(-record_battle[i]);
            }
        }
        if(q_SB.empty()&&q_SG.empty())
            cout << "green and blue died\n";
        else if(q_SG.empty())
        {
            cout << "blue wins\n";
            while(!q_SB.empty())
            {
                cout << *q_SB.rbegin() << endl;
                q_SB.erase(q_SB.lower_bound(*q_SB.rbegin()));
            }
        }
        else
        {
            cout << "green wins\n";
            while(!q_SG.empty())
            {
                cout << *q_SG.rbegin() << endl;
                q_SG.erase(q_SG.lower_bound(*q_SG.rbegin()));
            }
        }
        if (test_case)
            cout << endl;
    }
    return 0;
}
```
###### tags: `UVA code` `cpp` `林基成-C++` `Awwwolf的刷題之路`