Hugh

门泊东吴万里船

0%

PAT-1014 Waiting in Line

Posted on In

1014 Waiting in Line

题意

一队列人到银行办理业务, 每个人办理业务时长不同, 银行有几个服务窗口，每个服务窗口允许固定的人数排队，排满之后，后面的人只能等着在办理的人结束，才能去排队。
哪个队列走就可以去排那个队列，银行的营业时间是8:00-17:000

分析

这道题就是一个排队入队出队问题，问题的难点怎样确定去排哪个队。
类似于多核CPU任务调度的问题

思路

用一个结构体来记录每个窗口的信息
ST_WINDOW{
int iTopFinishTime;
int iTotalTime;
queue quePeopleId;
};
iTopFinishTime 表示队列中最顶端的人何时服务结束
iTotalTime 表示这个队列总共服务的时长
quePeopleId 表示当前队列中的人
这样每次只需要找到当前所有窗口最小的iTopFinishTime，就是下次可排队的窗口

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cctype>
#include<algorithm>
#include<cmath>
#include <queue>
using namespace std;
struct ST_WINDOW{  //模拟服务窗口
    int iTopFinishTime;
    int iTotalTime;
    queue<int> quePeopleId;
};

int main()
{
    int iN, iM, iK, iQ;
    cin>> iN >> iM >> iK >> iQ;
    ST_WINDOW stWindow[iN]; //服务窗口
    int szProcessTime[iK]; //每个客户处理的时间
    int szFinishTime[iK]; //每个客户结束处理时间
    for(int iIndex = 0; iIndex < iK; iIndex ++)
    {
        cin >> szProcessTime[iIndex];
    }

    int iProcessingNum = min(iN * iM, iK); //可进入服务窗口排队的人
    for(int iIndex = 0 ; iIndex < iProcessingNum; iIndex++)
    {
        stWindow[iIndex % iN].quePeopleId.push(iIndex);
        if(iIndex < iN)
        {
            stWindow[iIndex % iN].iTopFinishTime = szProcessTime[iIndex];
            stWindow[iIndex % iN].iTotalTime = szProcessTime[iIndex];
        }
        else
        {
            stWindow[iIndex % iN].iTotalTime = stWindow[iIndex % iN].iTotalTime + szProcessTime[iIndex];
        }
        szFinishTime[iIndex] = stWindow[iIndex % iN].iTotalTime ;
    }
    for(int iIndex = iProcessingNum; iIndex < iK; iIndex++) //需要等待进入排队的人
    {
        int iMinTopFinishTimeWindow = 0;

        //寻找最小的顶端服务时间
        for(int jIndex = 1; jIndex < iN; jIndex ++)
        {
            if(stWindow[iMinTopFinishTimeWindow].iTopFinishTime > stWindow[jIndex].iTopFinishTime)
            {
                iMinTopFinishTimeWindow = jIndex;
            }
        }

        stWindow[iMinTopFinishTimeWindow].quePeopleId.pop();
        stWindow[iMinTopFinishTimeWindow].quePeopleId.push(iIndex);
        int iToProcePeopleId = stWindow[iMinTopFinishTimeWindow].quePeopleId.front();
        stWindow[iMinTopFinishTimeWindow].iTopFinishTime += szProcessTime[iToProcePeopleId];
        stWindow[iMinTopFinishTimeWindow].iTotalTime += szProcessTime[iIndex];
        szFinishTime[iIndex] = stWindow[iMinTopFinishTimeWindow].iTotalTime ;
    }
    int iQueryId;
    for(int iIndex = 0; iIndex < iQ; iIndex++)
    {
        cin>> iQueryId;
        if(szFinishTime[iQueryId - 1] - szProcessTime[iQueryId - 1]>= 540)
        {
            cout<<"Sorry";
        }
        else
        {
            printf("%02d:%02d", 8 + (szFinishTime[iQueryId - 1]) / 60 , (szFinishTime[iQueryId - 1] ) % 60);
        }
        if(iIndex<iQ-1) printf("\n");
    }
    return 0;
}