[SWEA] 2477 : 차량정비소
풀이
구현
배열과 큐와 벡터를 이용해 하란대로 그대로 구현했다.
결과가 92ms인데 다른 코드 중에 12ms가 있다.
더 효율적인 방법도 생각해봐야겠다.
디버깅없이 한번에 구현해서 맞혔다. 기분좋다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin>>T;
for(int tc=1;tc<=T;tc++){
vector<int> ans;
int n,m,k,a,b;
cin>>n>>m>>k>>a>>b;
int rc[21]={0}; //각접수처 처리시간
int ma[21]={0}; //각 정비소 처리시간
int pt[1001]={0}; //고객 도착시간
for(int i=1;i<=n;i++){
cin>>rc[i];
}
for(int i=1;i<=m;i++){
cin>>ma[i];
}
for(int i=1;i<=k;i++){
cin>>pt[i];
}
//고객 도착 큐 (고객번호)
priority_queue<int,vector<int>,greater<int>> q1;
//고객 정비대기 큐 (고객번호, 출신접수처)
queue<pair<int,int>> q2;
//접수처 벡터 (고객번호,남은시간)
vector<pair<int,int>> v1(21,{0,0});
//정비소 벡터 (고객번호,남은시간)
vector<pair<int,int>> v2(21,{0,0});
int t=0;
int finish=0;
while(finish<k){
//도착고객 큐에 넣기
for(int i=1;i<=k;i++){
if(pt[i]<=t){
q1.push(i);
pt[i]=10000;
}
}
//접수처에 도착대기중 고객 넣거나 남은시간1빼기->0되면 정비대기큐로
for(int i=1;i<=n;i++){
//비었으면 접수
if(v1[i].first==0){
if(!q1.empty()){
v1[i].first=q1.top();
v1[i].second=rc[i];
q1.pop();
}
}
//안비었으면 시간빼기
else{
//1뻄
//if 0되면
//빼고 if(!q1.empty())면 바로추가
v1[i].second--;
if(v1[i].second==0){
q2.push({v1[i].first,i});
v1[i].first=0;
if(!q1.empty()){
v1[i].first=q1.top();
v1[i].second=rc[i];
q1.pop();
}
}
}
}
//정비소에 정비대기중 고객 넣거나 남은시간1빼기->0되면 비움(finish추가)
//고객을 넣을때 출신접수처(q2의 second)가 a이면서 b정비소로 가면
//ans벡터에 넣기.
for(int i=1;i<=m;i++){
//비었으면 정비
if(v2[i].first==0){
if(!q2.empty()){
v2[i].first=q2.front().first;
v2[i].second=ma[i];
if(a==q2.front().second && b==i){
ans.push_back(q2.front().first);
}
q2.pop();
}
}
//안비었으면 시간빼기
else{
v2[i].second--;
if(v2[i].second==0){
finish++;
v2[i].first=0;
if(!q2.empty()){
v2[i].first=q2.front().first;
v2[i].second=ma[i];
if(a==q2.front().second && b==i){
ans.push_back(q2.front().first);
}
q2.pop();
}
}
}
}
t++;
}
int sum=0;
if(ans.size()==0)
sum=-1;
for(int i=0;i<ans.size();i++){
sum+=ans[i];
}
cout<<'#'<<tc<<' '<<sum<<'\n';
}
return 0;
}
Written on March 27, 2019