[D3] 9280. 진용이네 주차타워

차고 같은 경우, 무조건 작은 인덱스 차고부터 써야되니 자료형 vector를 이용해 역순으로 정렬해줘서 사용했다.

대기자 같은 경우, 큐 자료 구조를 이용하여 FIFO을 구현하였다.

 

#include<stdio.h>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;

int car_box[101][2] = { 0 };
int car[2001][2] = { 0 };
queue<int> stack;
int price = 0;
int n;
int m;
vector<int> list;

int fill(int index) {
	if (!list.empty()) {
		car[index][1] = list.back();
		car_box[list.back()][1] = index;
		price += car_box[list.back()][0] * car[index][0];
		list.pop_back();
		return 1;
	}
	else {
		if(stack.empty()||stack.front()!=index)
			stack.push(index);
	}
	return 0;
}
int main(void) {
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);
	int tc = 0;
	cin >> tc;
	for (int p = 0; p < tc; p++) {
	
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			cin >> car_box[i][0];
			car_box[i][1] = 0;
			list.push_back(i);
		}
		for (int i = 1; i <= m; i++) {
			cin >> car[i][0];
			car[i][1] = 0;
		}
		sort(list.begin(), list.end(), greater<int>());
		for (int i = 1; i <= 2*m; i++) {
			int index = 0;
			cin >> index;
			if (index>=0) {
				fill(index);
			}
			else {
				index = -index;
				car_box[car[index][1]][1] = 0;
				list.push_back(car[index][1]);
				sort(list.begin(), list.end(), greater<int>());
				car[index][1] = 0;
				while (!stack.empty()) {
					if (fill(stack.front())) {
						stack.pop();
					}
					else {
						break;
					}
				}
			}
		}
		cout << "#"<<p+1<<" "<<price<<endl;
		price = 0;
		for (int i = 1; i <= n; i++) {
			list.pop_back();
		}
	}
	return 0;
}