PAT A1014 Waiting in Line (30 分) 模拟

       题目大意:银行有N个窗口,每个窗口最多排队M个人。假设有K个人都从8:00开始等待办理业务,并给出处理每个人业务的时间。前 N * M个人依次在N个窗口前排队,后面的人按照顺序,只有在某个窗口有空出位置时(人数小于M时),到该窗口排队。如果有多个窗口同时空出,选择序号小的。求出每个人结束业务的时间,注意如果某个人在17:00前还没有开始办理业务的话,他就不能办理业务了。

      用N个队列  queue<int> q[N] 表示窗口,首先将 min(N*M, K)个人按顺序放到这N个队列里,每个队列的pop时间即为队首元素需要处理业务的时间。对于剩下的 K - N*M 个人,依次处理。首先找到最早空出的窗口,然后将该队列pop,再push正在处理的人,然后更新该队列的pop时间。

      不过这样存在的问题是最后加入队列的人的开始时间没法更新,为了方便起见,另外设置N个队列 queue<int> calTime[N] ,进行相同的push操作,而不进行pop操作。这样当所有人处理完毕后,calTime[N] 就完整地存储了所有人所在的队列信息。计算时间用 calTime[N] 即可。

AC代码如下:

#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>

using namespace std;

const int MAXN = 21;
queue<int> q[MAXN];
queue<int> calTime[MAXN];
int popTime[MAXN] = {0};

void printTime(int startTime, int needTime)
{
    if(startTime >= (17 - 8) * 60) printf("Sorry\n");
    else
    {
        int hour = 8 + (startTime + needTime) / 60;
        int min = (startTime + needTime) % 60;
        printf("%02d:%02d\n", hour, min);
    }
}

int main()
{
    int N, M, K, Q;
    cin >> N >> M >> K >> Q;
    vector<int> needTime(K);
    vector<int> serveTime(K);
    for (int i = 0; i < K; ++i)
    {
        scanf("%d", &needTime[i]);
    }
    for (int i = 0; i < N * M && i < K; ++i)
    {
        q[i % N].push(i);
        calTime[i % N].push(i);
        if(q[i % N].size() == 1) popTime[i % N] += needTime[q[i % N].front()];
    }
    for (int i = N * M ; i < K; ++i)
    {
        int minIndex = 0, minTime = 0x7FFFFFFF;
        for (int j = 0; j < N; ++j)
        {
            if(popTime[j] < minTime)
            {
                minTime = popTime[j];
                minIndex = j;
            }
        }
        q[minIndex].pop();
        q[minIndex].push(i);
        calTime[minIndex].push(i);
        popTime[minIndex] += needTime[q[minIndex].front()];
    }
    for (int i = 0; i < N; ++i)
    {
        int end = 0;
        while(!calTime[i].empty())
        {
            serveTime[calTime[i].front()] = end;
            end += needTime[calTime[i].front()];
            calTime[i].pop();
        }
    }
    for (int query = 0; query < Q; ++query)
    {
        int index;
        scanf("%d", &index);
        index--;
        printTime(serveTime[index], needTime[index]);
    }
    return 0;
}


 

上一篇:模拟15 题解(waiting)


下一篇:Docker安装Mysql镜像报错(Get https://registry-1.docker.io/v2/: net/http: request canceled while waiting fo)