1026 Table Tennis （30 分)

2019-03-13

1026 Table Tennis （30 分)

A table tennis club has N tables available to the public. The tables are numbered from 1 to N. For any pair of players, if there are some tables open when they arrive, they will be assigned to the available table with the smallest number. If all the tables are occupied, they will have to wait in a queue. It is assumed that every pair of players can play for at most 2 hours.

Your job is to count for everyone in queue their waiting time, and for each table the number of players it has served for the day.

One thing that makes this procedure a bit complicated is that the club reserves some tables for their VIP members. When a VIP table is open, the first VIP pair in the queue will have the priviledge to take it. However, if there is no VIP in the queue, the next pair of players can take it. On the other hand, if when it is the turn of a VIP pair, yet no VIP table is available, they can be assigned as any ordinary players.

Input Specification:

Each input file contains one test case. For each case, the first line contains an integer N (≤10000) - the total number of pairs of players. Then N lines follow, each contains 2 times and a VIP tag: HH:MM:SS - the arriving time, P - the playing time in minutes of a pair of players, and tag - which is 1 if they hold a VIP card, or 0 if not. It is guaranteed that the arriving time is between 08:00:00 and 21:00:00 while the club is open. It is assumed that no two customers arrives at the same time. Following the players’ info, there are 2 positive integers: K (≤100) - the number of tables, and M (< K) - the number of VIP tables. The last line contains M table numbers.

Output Specification:

For each test case, first print the arriving time, serving time and the waiting time for each pair of players in the format shown by the sample. Then print in a line the number of players served by each table. Notice that the output must be listed in chronological order of the serving time. The waiting time must be rounded up to an integer minute(s). If one cannot get a table before the closing time, their information must NOT be printed.

Sample Input:

9
20:52:00 10 0
08:00:00 20 0
08:02:00 30 0
20:51:00 10 0
08:10:00 5 0
08:12:00 10 1
20:50:00 10 0
08:01:30 15 1
20:53:00 10 1
3 1
2

Sample Output:

08:00:00 08:00:00 0
08:01:30 08:01:30 0
08:02:00 08:02:00 0
08:12:00 08:16:30 5
08:10:00 08:20:00 10
20:50:00 20:50:00 0
20:51:00 20:51:00 0
20:52:00 20:52:00 0
3 3 2

作者: CHEN, Yue

单位: 浙江大学

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

一个乒乓球馆有n个球台，当有顾客到达时，会被分配到编号最小的可用球台。如果所有球台都不可用，则需要排队等待。输出顾客到达时间，服务时间，以及等待的时间。最后输出每张球桌服务的顾客数。注意如果顾客被服务的时间晚于21点，是不输出的。

坑点：

球馆有若干张vip球台，当vip球台可用时，优先给队伍中的vip顾客使用。若队伍中无vip顾客，则vip球台可以给普通顾客使用。当有多张球台同时可以使用时，vip顾客被安排至vip球台。

分析

无需算法知识，由于vip的存在，逻辑较繁琐

程序逻辑如下：

1.使用cus结构体，纪录顾客信息（到达时间，打球时间，是否vip，服务时间，是否被服务过了）

2.使用table数组，标记球桌的可用时间，初始化为8点钟。使用vip数组，标记是否vip球桌

3.被服务顾客小于n时，循环：

每次循环球桌，找到第一个空闲的球桌。接着循环顾客，找到队首顾客。接着分类讨论

1.如果球桌是vip桌，则分配给队伍中第一个vip。

2.非vip桌，继续分第一个顾客是否vip。

2.1顾客是vip，且同时有vip桌可用，为其分配vip桌。

2.2队首不是vip，则分配给第一个空闲桌即可。

4.根据被服务时间排序，输出。这里注意桌号从1开始记的，一开始没注意，从0开始，顾客信息是对的，但是每桌顾客数出错，排查了好久，发现桌号是1开始。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <cstring>
#include <cmath>
#include<sstream>

using namespace std;

struct cus{
    int arr;
    int play;
    int vip;
    int serv;
    int servd;
};

bool cmp(cus c1,cus c2){
    return c1.arr<c2.arr;
}

bool cmpbyserv(cus c1,cus c2){
    return c1.serv<c2.serv;
}
int main() {
    int n,table[110]={},isvip[110]={},t,v,ts,servd=0,tableserv[110]={};
    cin>>n;
    vector<cus> que(n);
    for(int i=0;i<n;i++){
        int hh,mm,ss;
        scanf("%d:%d:%d",&hh,&mm,&ss);
        int t=hh*3600+mm*60+ss;
        if(t>21*3600)
            continue;
        que[i].arr=t;
        cin>>que[i].play>>que[i].vip;
        if(que[i].play>120)
            que[i].play=120;
        que[i].play*=60;
    }
    cin>>ts>>v;
    for(int i=1;i<=v;i++){
        cin>>t;
        isvip[t]=1;
    }
    fill(table,table+110,8*3600);
    sort(que.begin(),que.end(),cmp);
    n=que.size();


    while(servd!=n){

        int i,v;
        int choice=0;
        int maxt=9999999999;
        //第一个空闲桌
        for(int i=1;i<=ts;i++) {
            if (table[i] < maxt) {
                choice = i;
                maxt = table[i];
            }
        }

        for(i=0;i<n;i++)
            if(que[i].servd==0)
                break;
        if(isvip[choice]){
            //vip桌，分配给第一个排队的VIP
            for(v=0;v<n;v++) {
                if (que[v].servd == 0 && que[v].vip == 1&&que[v].arr<table[choice])
                    break;
            }
            if(v!=n)
                i=v;
        }
        else{//非vip桌
            for(v=0;v<n;v++)
                if(que[v].servd==0)
                    break;
                //第一个人是vip
                if(que[v].vip==1){
                    for(int i=1;i<=ts;i++)
                        if(table[i]<=que[v].arr&&isvip[i]){
                            choice=i;
                            break;
                        }
                    if(v!=n)
                        i=v;
                }
        }
        servd++;
        que[i].servd=1;
        que[i].serv=max(que[i].arr,table[choice]);
        if(que[i].serv<21*3600) {
            table[choice] = que[i].serv + que[i].play;
            tableserv[choice]++;
        }
    }
    sort(que.begin(),que.end(),cmpbyserv);
    for(auto c:que){
        if(c.serv<21*3600) {
            int hh, mm, ss;
            hh = c.arr / 3600;
            mm = (c.arr - hh * 3600) / 60;
            ss = c.arr - hh * 3600 - mm * 60;

            printf("%02d:%02d:%02d ", hh, mm, ss);
            hh = c.serv / 3600;
            mm = (c.serv - hh * 3600) / 60;
            ss = c.serv - hh * 3600 - mm * 60;
            printf("%02d:%02d:%02d ", hh, mm, ss);
            double x=(c.serv - c.arr) ;

            cout << int(x/60.0+0.5)<< endl;
        }
    }
    cout<<tableserv[1];
    for(int i=2;i<=ts;i++)
        cout<<" "<<tableserv[i];
    return 0;
}