PAT甲级1026.

目录

A1026

题目

样例

输入:

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

输出:

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

思路和坑点

　　服务队列模拟，使用结构体数组的方式表示多个桌子，每个桌子结构体中包含桌子当前服务的结束时间，桌子服务的人数统计。顾客分成vip和非vip队列，这里利用map容器的成对儿存放，并且自身有序，因此用其表示顾客队列。
　　坑点
　　桌子服务的判定标准是，队列中有人，且已经在等候。桌子空闲的标志是该桌子当前服务结束时间小于等于当前的时间。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define st 8*3600
#define ed 21*3600

typedef struct table{                       //桌子结构体 
    int edtime,cnt,tag;                     //当前服务的结束时间，服务人数统计，vip标记 
    table():edtime(st),cnt(0),tag(0){}      //初始化 
}Table;
void Print(int i){
    printf("%02d:%02d:%02d",i/3600,i/60%60,i%60);    //打印时间 
}
vector<Table> T;                            //桌子的数组 
map<int,int> mpo,mpv;                       //map表示的顾客服务队列 
void check(int j,int time,map<int,int> &mp){    //使用传引用的方式，对不同的队列进行判断是都要从中取出顾客进行服务 
    if(mp.size()){                          //非空 
        auto it=mp.begin();                    
        if(it->first<=time){                //队头顾客已经在等待，进行服务，打印并更新队列参数 
            T[j].edtime=time+it->second;
            T[j].cnt++;
            Print(it->first); putchar(' ');
            Print(time);           putchar(' '); 
            printf("%d\n",(time-it->first+30)/60);
            mp.erase(it);
        }
    }
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){                   //读入 
        int hh,mm,ss,cost,tag;
        scanf("%d:%d:%d %d %d",&hh,&mm,&ss,&cost,&tag);
        cost=cost>120?120*60:cost*60;
        if(tag==0)
            mpo[hh*3600+mm*60+ss]=cost;    //普通用户入队 
        else    
            mpv[hh*3600+mm*60+ss]=cost;    //vip用户入队 
    }
    int k,m;
    scanf("%d %d",&k,&m);
    T.resize(k);
    for(int i=0;i<m;i++){                   //vip桌子的标记 
        int temp;
        scanf("%d",&temp);
        T[temp-1].tag=1;
    }
    for(int i=st;i<ed;i++){
        for(int j=0;j<k;j++){               //优先遍历一遍为vip顾客进行服务判定 
            if(T[j].edtime<=i&&T[j].tag==1){
                check(j,i,mpv);
                if(mpv.size()==0) break;    //vip服务全部完成时，提前结束循环 
            }
        }
        for(int j=0;j<k;j++){               //安排了vip之后，全员进行判定 
            if(T[j].edtime<=i){
                if(mpo.size()&&mpv.size()){                        //如果都不空，取来的早的进行判定 
                    auto it=mpo.begin(),itv=mpv.begin();
                    if(it->first<itv->first)
                        check(j,i,mpo);
                    else if(it->first>itv->first)
                        check(j,i,mpv);
                }
                else if(mpo.size())                                //如果有一个空，非空的进行判定 
                    check(j,i,mpo);
                else if(mpv.size())
                    check(j,i,mpv);
                else break;                                        //都空则，提前结束，表示顾客已经服务完毕 
            }
        }
        if(mpo.size()==0&&mpv.size()==0)    break;
    }
    for(int i=0;i<k;i++){                                        //打印服务人数 
        if(i) putchar(' ');
        printf("%d",T[i].cnt);
    }
    return 0;
}