题目:https://www.patest.cn/contests/pat-a-practise/1014
思路:
直接模拟类的题。
线内的各个窗口各为一个队,线外的为一个,按时间模拟出队、入队。
注意点:即使到关门时间,已经在服务中的客户(窗口第一个,接待时间早于关门时间)还是可以被服务的。其它的则不服务。
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std; int N;// (<=20, number of windows)
int M;// (<=10, the maximum capacity of each line inside the yellow line)
int K;// (<=1000, number of customers)
int Q;// (<=1000, number of customer queries)
#define INF 0x6FFFFFFF
typedef struct Customer
{
int process;
int leave;
}Customer; int main()
{
//input
scanf("%d%d%d%d",&N,&M,&K,&Q);
vector<Customer> cus(K);
for(int i = ; i < K; ++i)
{
scanf("%d", &cus[i].process);
cus[i].leave = INF;
}
//process
vector<queue<int>> winQueue(N);
vector<int> timeBase(N, );
int p;
for(p = ; p < N*M && p < K; ++p)
{
cus[p].leave = timeBase[p%N]+cus[p].process;
timeBase[p%N] = cus[p].leave;
winQueue[p%N].push(p);
}
//for somebody out of the normal queue
for(; p < K; ++p)
{
int mmin = INF;
int index = -;
for(int j = ; j < N; ++j)
{
int top = winQueue[j].front();
if(mmin > cus[top].leave)
{
index = j;
mmin = cus[top].leave;
}
}
//then pop
cus[p].leave = timeBase[index]+cus[p].process;
timeBase[index] = cus[p].leave;
winQueue[index].pop();
winQueue[index].push(p);
} //query
for(int i = ; i < Q; ++i)
{
int q;
scanf("%d",&q);
q--;
if(cus[q].leave-cus[q].process >= )
printf("Sorry\n");
else
printf("%02d:%02d\n", +cus[q].leave/, cus[q].leave%);
}
return ;
}