PAT甲級1026

1026. Table Tennis (30)

時間限制

400 ms

記憶體限制

65536 kB

代碼長度限制

16000 B

判題程式

Standard

作者

CHEN, Yue

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:0008:00:000

08:01:30 08:01:30 0

08:02:00 08:02:000

08:12:0008:16:30 5

08:10:00 08:20:00 10

20:50:0020:50:00 0

20:51:00 20:51:00 

20:52:00 20:52:00 0

3 3 2

#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int K = 111;//視窗數
const int INF = 1000000000;//無窮大
struct Player
{
  int arriveTime, startTime, trainTime;//到達時間、訓練開始時間及訓練時長
  bool isVIP;//是否是VIP球員
}newPlayer;//臨時存放新讀入的球員
struct Table
{
  int endTime, numServe;//目前占用該球桌的球員的結束時間及已訓練的人數
  bool isVIP;//是否是VIP球桌
}table[K];//K個球桌
vector<Player> player;//球員隊列
int convertTime(int h, int m, int s)
{
  return h * 3600 + m * 60 + s;//将時間轉換為以s為機關，友善比較和計算
}
bool cmpArriveTime(Player a, Player b)
{
  return a.arriveTime < b.arriveTime;//按到達時間排序
}
bool cmpStartTime(Player a, Player b)
{
  return a.startTime < b.startTime;//按開始時間排序
}
//編号VIP從目前VIP球員移到下一個VIP球員
int nextVIPPlayer(int VIPi)
{
  VIPi++;//先将VIPi加1
  while (VIPi < player.size() && player[VIPi].isVIP == 0)
  {
    VIPi++;//隻要目前球員不是VIP，就讓VIPi後移一位
  }
  return VIPi;//傳回下一個VIP球員的ID
}
//将編号為tID的球桌配置設定給編号為pID的球員
void allotTable(int pID, int tID)
{
  if (player[pID].arriveTime <= table[tID].endTime)//更新球員的開始時間
  {
    player[pID].startTime = table[tID].endTime;
  }
  else
  {
    player[pID].startTime = player[pID].arriveTime;
  }
  //該球桌的訓練結束時間更新為新球員的結束時間，并讓服務人數加1
  table[tID].endTime = player[pID].startTime + player[pID].trainTime;
  table[tID].numServe++;
}
int main()
{
  int n, k, m, VIPtable;
  scanf("%d", &n);//球員數
  int stTime = convertTime(8, 0, 0);//開門時間為8點
  int edTime = convertTime(21, 0, 0);//關門時間為21點
  for (int i = 0; i < n; i++)
  {
    int h, m, s, trainTime, isVIP;//時、分、秒、訓練時長、是否是VIP球員
    scanf("%d:%d:%d %d %d", &h, &m, &s, &trainTime, &isVIP);
    newPlayer.arriveTime = convertTime(h, m, s);//到達時間
    newPlayer.startTime = edTime;//開始時間初始化為21點
    if (newPlayer.arriveTime >= edTime) continue;//21點及以後的直接排除
    //訓練時長
    newPlayer.trainTime = trainTime <= 120 ? trainTime * 60 : 7200;
    newPlayer.isVIP = isVIP;//是否是VIP
    player.push_back(newPlayer);//将newPlayer加入到球員隊列中
  }
  scanf("%d%d", &k, &m);//球桌數及VIP球桌數
  for (int i = 1; i <= k; i++)
  {
    table[i].endTime = stTime;//目前訓練結束時間為8點
    table[i].numServe = table[i].isVIP = 0;//初始化numServe與isVIP
  }
  for (int i = 0; i < m; i++)
  {
    scanf("%d", &VIPtable);//VIP球桌編号
    table[VIPtable].isVIP = 1;//記為VIP球桌
  }
  sort(player.begin(), player.end(), cmpArriveTime);//按到達時間排序
  int i = 0, VIPi = -1;//i用來掃描所有球員，VIPi總是指向目前最前的VIP球員
  VIPi = nextVIPPlayer(VIPi);//找到第一個VIP球員
  while (i < player.size())//目前隊列最前面的球員為i
  {
    int idx = -1, minEndTime = INF;//尋找最早能空閑的球桌
    for (int j = 1; j <= k; j++)
    {
      if (table[j].endTime < minEndTime)
      {
        minEndTime = table[j].endTime;
        idx = j;
      }
    }
    //idx為最早空閑的球桌編号
    if (table[idx].endTime >= edTime)break;//已經關門，直接break
    if (player[i].isVIP == 1 && i < VIPi)
    {
      i++;//如果i号是VIP球員，但是VIPi>i,說明i号球員已經在訓練
      continue;
    }
    //以下按球桌是否是VIP、球員是否是VIP，進行4種情況讨論
    if (table[idx].isVIP == 1)
    {
      if (player[i].isVIP == 1)//①球桌是VIP，球員是VIP
      {
        allotTable(i, idx);//将球桌idx配置設定給球員i
        if (VIPi == i)VIPi = nextVIPPlayer(VIPi);//找到下一個VIP球員
        i++;//i号球員開始訓練，是以繼續隊列的下一個人
      }
      else
      {//如果目前隊首的VIP球員比該VIP球桌早，就把球桌idx配置設定給他
        if (VIPi < player.size() && player[VIPi].arriveTime <= table[idx].endTime)
        {
          allotTable(VIPi, idx);//将球桌idx配置設定給球員i
          VIPi = nextVIPPlayer(VIPi);//找到下一個VIP球員
        }
        else
        {//隊首VIP球員比該VIP球桌遲，仍然把球桌idx配置設定給球員i
          allotTable(i, idx);//将球桌idx配置設定給球員i
          i++;//i号球員開始訓練，是以繼續隊列的下一個人
        }
      }
    }
    else
    {
      if (player[i].isVIP == 0)//③球桌不是VIP，球員不是VIP
      {
        allotTable(i, idx);//将球桌idx配置設定給球員i
        i++;//i号球員開始訓練，是以繼續隊列的下一個人
      }
      else
      {//④球桌不是VIP，球員是VIP
        //找到最早空閑的VIP球桌
        int VIPidx = -1, minVIPEndTime = INF;
        for (int j = 1; j <= k; j++)
        {
          if (table[j].isVIP == 1 && table[j].endTime < minVIPEndTime)
          {
            minVIPEndTime = table[j].endTime;
            VIPidx = j;
          }
        }
        //最早空閑的VIP球桌編号是VIPidx
        if (VIPidx != -1 && player[i].arriveTime >= table[VIPidx].endTime)
        {//如果VIP球桌存在，且空閑時間比球員來的時間早
        //就把它配置設定給球員i
          allotTable(i, VIPidx);
          if (VIPi == i)VIPi = nextVIPPlayer(VIPi);//找到下一個VIP球員
          i++;//i号球員開始訓練，是以繼續隊列的下一個人
        }
        else
        {
          //如果球員來時VIP球桌還未空閑，就把球桌idx配置設定給他
          allotTable(i, idx);
          if (VIPi == i)VIPi = nextVIPPlayer(VIPi);//找到下一個VIP球員
          i++;//i号球員開始訓練，是以繼續隊列的下一個人
        }
      }
    }
  }
  sort(player.begin(), player.end(), cmpStartTime);//按開始時間排序
  for (int i = 0; i < player.size() && player[i].startTime < edTime; i++)//輸出
  {
    int t1 = player[i].arriveTime;
    int t2 = player[i].startTime;
    printf("%02d:%02d:%02d ", t1 / 3600, t1 % 3600 / 60, t1 % 60);
    printf("%02d:%02d:%02d ", t2 / 3600, t2 % 3600 / 60, t2 % 60);
    printf("%.0f\n", round((t2 - t1) / 60.0));
  }
  for (int i = 1; i <= k; i++)
  {
    printf("%d", table[i].numServe);
    if (i < k)printf(" ");
  }
  return 0;
}