题目:http://pat.zju.edu.cn/contests/pat-a-practise/1017
题解:
模拟题。
代码:
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<algorithm> using namespace std; #define INF 0x6fffffff struct customer { int start;//开始处理时间 int leave;//结束处理时间 int process;//处理所需时间 int time;//到达时间 }cust[10005]; int windows[105];//当前窗口可以处理的最早时间 vector<struct customer> q[105]; bool cmp(const struct customer &a,const struct customer &b) { return a.time<b.time; } int main() { int n,k; int h,m,s; int minx,idx; double summ; scanf("%d%d",&n,&k); for(int i=0;i<k;++i) windows[i]=8*60*60; for(int i=0;i<n;++i) { scanf("%d:%d:%d%d",&h,&m,&s,&cust[i].process); cust[i].process*=60; cust[i].time=((h*60)+m)*60+s; } sort(cust,cust+n,cmp); for(int i=0;i<n;++i) { minx=INF; for(int j=0;j<k;++j) { if(minx>windows[j]) { minx=windows[j]; idx=j; } } cust[i].start=max(windows[idx],cust[i].time); cust[i].leave=cust[i].start+cust[i].process; windows[idx]=cust[i].leave; } m=n; summ=0; for(int i=0;i<n;++i) if(cust[i].time<=17*60*60) summ+=(cust[i].start-cust[i].time);//开始处理时间减去到达时间 else --m;//该客户无法处理,分母减一 if(summ>0) printf("%.1f\n",summ/60.0/m); else printf("0.0\n");//没有客户可以处理 return 0; }