PAT1017. Queueing at Bank

xiaoxiao2021-03-25 108

#include <iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<map> #include<string> #include<vector> using namespace std; const int maxn=10010; const int maxm=110; int n,k; struct cus { int arr;//顾客到达时间 int p; int w;//顾客等待时间 } c[maxn]; struct window { int u;//该窗口现在的人业务完成的时间 } win[maxm]; bool cmp(cus a,cus b) { return a.arr<b.arr;//根据先来后到顾客排成一列 } int cal(int h1,int m1,int s1,int h2,int m2,int s2)//计算从h1:m1:s1到h2:m2:s2需要多少秒 { int ans=0; while(h1<h2||m1<m2||s1<s2) { s1++; ans++; if(s1==60) { s1=0; m1++; } if(m1==60) { h1++; m1=0; } } return ans; } int main() { // freopen("d://jin.txt","r",stdin); cin>>n>>k; int h,m,s; for(int i=0; i<n; i++) { scanf("%d:%d:%d %d",&h,&m,&s,&c[i].p); if(h>=8)c[i].arr=cal(8,0,0,h,m,s); else c[i].arr-=cal(h,m,s,8,0,0);//计算顾客到达的时间 } sort(c,c+n,cmp); for(int i=0; i<k; i++) { c[i].w=max(0,-c[i].arr);//前K个顾客等待时间 win[i].u=max(c[i].p*60,c[i].p*60+c[i].arr);//前K个窗口业务完成的时间 } for(int i=k; i<n; i++) { int min=100000000; int ch; for(int j=0; j<k; j++) { if(win[j].u<min)//选择业务完成最快的窗口 { min=win[j].u; ch=j; } } c[i].w=max(0,win[ch].u-c[i].arr);//新进来的人计算等待的时间 win[ch].u=max(win[ch].u,c[i].arr)+c[i].p*60;//更新业务完成的时间 } double ans=0; int people=0; for(int i=0; i<n; i++) { if(c[i].arr<32401)//去掉17：01分包括在内的人 { ans+=c[i].w; people++; } } ans/=60.0; printf("%.1f",ans/people); return 0; }

转载请注明原文地址: https://ju.6miu.com/read-12418.html

技术

最新回复(0)