SW 2477 차량 정비소 문제

/*

접수 창구번호, 정비 창구번호

N개 접수 창구, M개 정비 창구

접수 창구 i에서 고객 한 명의 고장을 접수하는 데 걸리는 시간 ai (1<=i<=N)

정비 창구 j에서 고객 한 명의 차량을 정비하는 데 걸리는 시간 bj (1<=j<=M)

지금까지 방문한 고객의 K명

고객번호 k인 고객이 차량 정비소에 도착하는 시간은 tk이다. (1<=k<=K)

접수 창구의 우선순위는 아래와 같다.

① 여러 고객이 기다리고 있는 경우 고객번호가 낮은 순서대로 우선 접수한다.

② 빈 창구가 여러 곳인 경우 접수 창구번호가 작은 곳으로 간다.

정비 창구의 우선순위는 아래와 같다.

① 먼저 기다리는 고객이 우선한다.

② 두 명 이상의 고객들이 접수 창구에서 동시에 접수를 완료하고 정비 창구로 이동한 경우, 이용했던 접수 창구번호가 작은 고객이 우선한다.

③ 빈 창구가 여러 곳인 경우 정비 창구번호가 작은 곳으로 간다.

고객의 도착 시간 tk, 접수 창구의 처리 시간 ai, 정비 창구의 처리 시간 bj가 주어졌을 때, 지갑을 분실한 고객과 같은 접수 창구와 같은 정비 창구를 이용한 고객의 고객번호들을 찾아 그 합을 출력하는 프로그램을 작성하라.

만약, 그런 고객이 없는 경우 -1을 출력한다.

*/

#include <cstdio>

#include <queue>

#include <iostream>

#define MAX 11

#define KMAX 1010

using namespace std;

int T, N, M, A, B; // 1<= N,M <= 9

int K; // 2<= K <= 1000

//1<= ai <=20,  1<= bj <= 20, 0<= tk<= 1000

int receptionArr[MAX][3];

int repairArr[MAX][3];

int visitArr[KMAX][2];

int visit_total_cnt = 0, visit_cnt=1;

int Aarr[KMAX], Aarr_cnt=0;

int ans = 0;

queue<int> queue1, queue2;

void init(){

visit_total_cnt = 0, visit_cnt = 1;

Aarr_cnt = 0;

ans = 0;

for (int i = 1; i <= MAX-1; i++) ///이부분에서 -1 안해서 에러났었음. 이제는 정상작동함.

Aarr[i] = 0;

for (int i = 1; i <= KMAX-1; i++){

visitArr[i][0] = 0;

visitArr[i][1] = 0;

}

for (int i = 1; i <= MAX-1; i++){

receptionArr[i][0] = 0;

receptionArr[i][1] = 0;

receptionArr[i][2] = 0;

}

for (int i = 1; i <= MAX - 1; i++){

repairArr[i][0] = 0;

repairArr[i][1] = 0;

repairArr[i][2] = 0;

}

}

//B정비창구에 방문했던 사람이 A접수창구에도 방문하였다면 고객넘버를 더한다.

void checkAns(int number){

for (int i = 1; i <= Aarr_cnt; i++){

if (number == Aarr[i]) ans += number;

}

}

void solve(){

while (1){

bool break_check1 = true, break_check2=true;

/*

용무를 끝낸 사람을 먼저 꺼내는게 우선

*/

//정비열에서 일을 마친 사람을 제거한다.

for (int j = 1; j <= M; j++){

//cnt가 0이 된 사람들 정비열에서 제거한다.

if (repairArr[j][0] != 0 && repairArr[j][1] == 0){

repairArr[j][0] = 0;

repairArr[j][1] = 0;

}

}

//접수열에서 일을 마친 사람을 정비열로 넘긴다.

for (int i = 1; i <= N; i++){

//cnt가 0이 된 사람들 다음 대기열로 넘긴다.

if (receptionArr[i][0] != 0 && receptionArr[i][1] == 0){

queue2.push(receptionArr[i][0]);

receptionArr[i][0] = 0;

receptionArr[i][1] = 0;

}

}

/*

빈 자리에 사람들을 집어넣는다.

*/

//대기열 처리

while(1){

//도착했다면 큐에 낮은 번호먼저 입력

if (visitArr[visit_cnt][1] == 0 && visit_cnt <= visit_total_cnt){

queue1.push(visit_cnt);

visit_cnt++;

}

else{ break; }

}

for (int i = 1; i <= N; i++){

//창구가 비어 있고, queue1에 대기하고 있는 사람이 있다면

if (receptionArr[i][0] == 0 && !queue1.empty()){

receptionArr[i][0] = queue1.front(); queue1.pop();

//특정 접수 창구에 온 손님들의 번호를 답을 구하기 위하여 저장한다.

if (i == A){ //A는 창구번호, I도 창구번호.

Aarr[++Aarr_cnt] = receptionArr[i][0];////////////////////////////////////////////////////////////////////////////////////

}

receptionArr[i][1] = receptionArr[i][2];

}

if (receptionArr[i][0] != 0) { break_check1 = false; } //접수창구에 있는 사람이 있다면 종료하면 안된다.

}

for (int j = 1; j <= M; j++){

//queue2에 대기하는 사람이 있고, 비어있는 정비창구가 있다면 사람 넣기

if (!queue2.empty() && repairArr[j][0] == 0){

repairArr[j][0] = queue2.front(); queue2.pop();

//특정 정비창구에 온 사람이 특정 접수 창구에도 갔었다면 해당 고객 번호가 답이므로 고객번호 더하기 처리

if(j==B){

checkAns(repairArr[j][0]);

}

repairArr[j][1] = repairArr[j][2];

}

if (repairArr[j][0] != 0) { break_check2 = false; } //정비창구에 있는 사람이 있다면 종료하면 안된다.

}

//제일 마지막에 전체 시간 카운트 감소 시키는 함수

//0초과되는 cnt만 줄여야 한다

for (int k = visit_cnt; k <= K; k++){ 

if (visitArr[k][1] >= 1){

visitArr[k][1]--;

}

}

for (int i = 1; i <= N; i++){

if (receptionArr[i][1] >= 1){

receptionArr[i][1]--;

}

}

for (int j = 1; j <=M; j++){

if (repairArr[j][1] >= 1){

repairArr[j][1]--;

}

}

//마지막 손님이 정비창구에서 나갔을 경우 함수 종료

if (visit_cnt > visit_total_cnt && break_check1 && break_check2)

break;

}

}

int main()

{

scanf("%d", &T);

for (int tc = 1; tc <= T; tc++){

init();

scanf("%d %d %d %d %d", &N, &M, &K, &A, &B);

for (int i = 1; i <= N; i++)

scanf("%d", &receptionArr[i][2]);

for (int j = 1; j <= M; j++)

scanf("%d", &repairArr[j][2]);

for (int k = 1; k <= K; k++){

visitArr[k][0] = ++visit_total_cnt;

scanf("%d", &visitArr[k][1]);

}

solve();

if (ans == 0) ans = -1; //두 창구 모두 들어온 번호가 없다면 -1

printf("#%d %d \n", tc, ans);

}

return 0;

}