PAT甲级1017.

目录

A1017

题目

样例

输入:

7 3
07:55:00 16
17:00:01 2
07:59:59 15
08:01:00 60
08:00:00 30
08:00:02 2
08:03:00 10

输出:

8.2

思路和坑点

　　将有效的顾客建立队列，这里利用map容器的有序性，直接使用map记录每位顾客，从而形成有序的队列，映射的值为顾客的时间花费，按照要求，每位顾客最长为60分钟，输入时直接处理。
　　另一个问题在于窗口的模拟，窗口使用数组记录每个窗口服务结束的时间，如果窗口到达结束时间，而且队伍不空，且队伍中的顾客已经到了，则入队服务并计算等待时间。
　　坑点
　　判定时间结束的的标志，应该是顾客队列空，而不是17点。因为所有的有效记录都是需要服务的，所以有可能有人17点之前到了，但是排到17点以后才接受服务，测试点5的情况便是如此。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define st 8*3600
#define ed 17*3600
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif
    int n,k;
    cin>>n>>k;
    map<int,int> custom;                            //顾客队列 
    vector<int> window(k,st);                       //窗口模拟 
    for(int i=0;i<n;i++){                           //输入 
        int h,m,s,cost;
        scanf("%d:%d:%d %d",&h,&m,&s,&cost);
        int begin=h*3600+m*60+s;
        if(begin<=ed){                              //有效记录才保存 
            cost=cost>60?3600:cost*60;              //服务时间上界判定 
            custom[begin]=cost;                     //保存记录 
        }
    }
    if(custom.size()==0){                           //队列如果没有人特判，因为0人无法平均 
        cout<<"0.0";
    }
    else{
        n=custom.size();
        int cnt=0;
        int flag=0;
        for(int time=st;;time++){                   //判定终点应该是顾客队列位空，而不是银行关门时间 
            for(int i=0;i<k;i++){
                if(custom.size()==0){               //队列空是退出循环 
                    flag=1;break;
                }
                if(window[i]<=time){                //窗口时间到时且队列中有人时 
                    auto it=custom.begin();         //去队首顾客进行服务 
                    if(it->first<=time){
                        cnt+=time-it->first;        //计算等待时间 
                        window[i]=time+it->second;  //更新窗口结束时间 
                        custom.erase(it);           //将纳入服务的顾客移出队列 
                    }
                }
            }
            if(flag==1)                            //循环结束判定，两层，因此判定两次 
                break;
        }
        
        printf("%.1f",1.0*cnt/(60*n));            
    }
    return 0;    
}