[C++知识库]PAT 1017 Queueing at Bank (25 分)

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct people{
    int come,time;
    people(int ss,int tt):come(ss),time(tt){}
};
bool cmp1(people a,people b){
    return a.come<b.come;
}
int main() {
    int n,k;
    cin>>n>>k;
    vector<people> p;
    for(int i=0;i<n;i++){
        int hh,mm,ss,tt;
        scanf("%d:%d:%d %d",&hh,&mm,&ss,&tt);
        int sum=(hh*60+mm)*60+ss;
        if(sum>61200) continue;
        p.push_back(people(sum,tt*60));
    }
    sort(p.begin(),p.end(),cmp1);   			//先来先服务
    int cnt=p.size(),waitTime=0;
    priority_queue<int ,vector<int>,greater<int>>q;   //q里int从小排到大, q.top()为k个窗口中的最早结束时间
    for(int i=0;i<k;i++) q.push(28800);   //8*3600 
    for(int i=0;i<cnt;i++){
        if(q.top()<=p[i].come){    			//无需等待
            q.push(p[i].come+p[i].time);	//更新窗口服务结束时间
            q.pop();						
        }else{
            waitTime+=q.top()-p[i].come;   //初次被服务时间-到达时间
            q.push(q.top()+p[i].time);
            q.pop();
        }
    }
    cnt?printf("%.1lf",(double)waitTime/60.0/(double)cnt):printf("0.0");
    return 0;
}