题目链接：点击打开链接
题目大意：有 N 个人，K 个服务窗口，按时间顺序进行排序，计算等待时间（开始时间 - 达到时间） + 业务时间。主循环用客户数量，与之前那题(1014)用时间控制为主循环不太一样。
Ps1：题目确保不会有相同时间达到的情况。
Ps2：题目所求客户平均等候时间，而不是平均在银行的时间。
解题思路：做这一类“银行排队”题目的问题一般处理步骤如下：
- 1、找主循环变量控制大局
- 2、初始化数据读入
- 3、初始化队伍
- 4、主循环
- 5、扫尾
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=10005; const int EI=8*3600; const int SEDONE=17*3600+1; struct peo { int ss,cos,ed,wait; friend bool operator<(peo p1,peo p2) { return p1.ed>p2.ed; // 小->大 } }peos[maxn]; priority_queue<peo> pq; int cmp(peo p1,peo p2) { return p1.ss<p2.ss; } int main() { int n,k,h,m,s,w; while(~scanf("%d%d",&n,&k)) { for(int i=0;i<n;i++) { scanf("%d:%d:%d%d",&h,&m,&s,&w); peos[i].ss=s+60*m+3600*h; peos[i].cos=w; } sort(peos,peos+n,cmp); while(!pq.empty()) pq.pop(); int l=0; peo p; for(int i=0;i<k;i++,l++) { p=peos[l]; peos[l].wait=EI>p.ss?EI-p.ss:0; peos[l].ed=p.cos*60+peos[l].wait+p.ss; pq.push(peos[l]); } int rs=0; while(l<n) { if(peos[l].ss>=SEDONE) break; p=pq.top(); pq.pop(); rs+=p.wait; peos[l].wait=p.ed>peos[l].ss?p.ed-peos[l].ss:0; peos[l].ed=peos[l].cos*60+peos[l].wait+peos[l].ss; pq.push(peos[l]); l++; } while(!pq.empty()) { p=pq.top(); pq.pop(); rs+=p.wait; } printf("%.1f\n",rs*1.0/60/l); } return 0; }
