23. UVa-978 Lemmings Battle! //multiset

문제

<그림1: 문제 설명>

영어 별로 안 어려우니까 읽자.

 

이 문제를 풀 때는 multiset자료구조를 이용하였는데 다음 두가지 이유 때문이다.

1. 매번 싸움마다 원소의 값이 가장 큰 놈을 알아야 한다. (& 그 놈만 알면 된다.)

2. 중복 원소를 허용해야 한다.

set은 1에 맞지만 2가 안 되기 때문에 중복 원소 허용의 multiset을 썼다.

주의할 점은 multiset의 erase함수를 value기반으로 사용하면 해당 value를 가진 모든 원소가 지워져버린다. 따라서 key를 기반으로 이 함수를 사용해야 의도한 결과를 낼 수 있다. (의도: 원소 하나만 삭제)

코드는 다음과 같다.

 

#include<iostream>
#include<set>

using namespace std;


int main() {
	int N, SG, SB,B,temp;
	cin >> N;
	while (N--) {
		multiset<int> Green;
		multiset<int>::iterator gsoldier = Green.begin();
		multiset<int> Blue;
		multiset<int>::iterator bsoldier = Blue.begin();
		cin >> B >> SG >> SB;
		for (int i = 0; i < SG; i++) {	//Green lemming input part
			cin >> temp;
			Green.insert(temp);

		}
		for (int i = 0; i < SB; i++) {	//Blue lemming input part
			cin >> temp;
			Blue.insert(temp);
		}	//smallest element lies at begin, largest element lies at end in set


		while (1) {	//Deadly War starts
			//ready for buffer
			int* blue_buffer = new int[B];
			int bbuf = 0;
			int* green_buffer = new int[B];
			int gbuf = 0;
			if (Green.size() == 0 || Blue.size() == 0) break;	//terminal condition of battle



			for (int i = 0; i < B; i++) {	//fighting part
				if (Green.size() == 0 || Blue.size() == 0) break;
				gsoldier = --Green.end();
				bsoldier = --Blue.end();
				if (*gsoldier > * bsoldier) {	//green soldier-> survives at lower power, blue soldier->erase
					temp = *gsoldier - *bsoldier;
					Blue.erase(bsoldier);
					Green.erase(gsoldier);
					green_buffer[gbuf++] = temp;
				}
				else if (*gsoldier < *bsoldier) {	//blue soldier ->survives at lower power, green soldier->erase
					temp = *bsoldier - *gsoldier;
					Blue.erase(bsoldier);
					Green.erase(gsoldier);
					blue_buffer[bbuf++] = temp;
//					const_cast<int&>(*bsoldier) = *bsoldier - *gsoldier; 이거 되나 확인
				}
				else {
					Green.erase(gsoldier);
					Blue.erase(bsoldier);
				}
			}
			for (int i = 0; i < bbuf; i++) {
				Blue.insert(blue_buffer[i]); 
			}
			for (int i = 0; i < gbuf; i++) {
				Green.insert(green_buffer[i]);
			}
	

			delete[] blue_buffer;
			delete[] green_buffer;
		}

		if (Green.size() == 0&&Blue.size() == 0) {
			cout << "green and blue died" << endl;
		}
		else if (Green.size() != 0) {
			cout << "green wins" << endl;
			for (gsoldier = --Green.end(); gsoldier != Green.begin();gsoldier--) {
				cout << *gsoldier << endl;
			}
			cout << *Green.begin() << endl;
		}
		else {
			cout << "blue wins" << endl;
			for (bsoldier = --Blue.end(); bsoldier != Blue.begin(); bsoldier--) {
				cout << *bsoldier << endl;
			}
			cout << *Blue.begin() << endl;
		}
		if(N!=0) cout << endl;
	}


}