1017 Queueing at Bank (25 分) 有很多错误的题解大家注意

本文主要是介绍1017 Queueing at Bank (25 分) 有很多错误的题解大家注意，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目分析：

有n个客户，k个窗口依次根据客户的到达顺序进行业务办理，类似于操作系统中的先来先服务算法，每个客户的办理时间不超过60min，很多题解说大于60就等于60的说法是错误，这里的样例就是不超过60min，是保证的。

解题思路：

好多题解都是找目前最快结束的窗口（可以考虑优先队列），我是统一起来根据秒从8点开始模拟，检测这一秒是否有客户办理完毕，以及是否有客户可以进行处理。时间复杂度是O（t*k），t是办理所需总时间，k是k个窗口。

题解代码：

#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[10001]={0};
int pt[10001];
int st[10001];
int ppt[10001];
struct node{int st;int ppt;int pt;int end;
};
bool cmp(node a,node b)
{return a.st<b.st;
}
int main()
{int n,k,sub=0;node array[10001];cin>>n>>k;int eta=(17-8)*3600;for(int i=1;i<=n;i++){	int h,min,s,p;scanf("%d:%d:%d %d",&h,&min,&s,&p);int temp=(h-8)*3600+min*60+s;if(temp>=eta)continue;array[sub].st=temp;//if(p>60)//p=60;array[sub].pt=p*60;array[sub].ppt=array[sub].pt;sub++;}sort(array,array+sub,cmp);
/*	for(int i=0;i<sub;i++){cout<<array[i].st<<" "<<array[i].pt<<" "<<endl;}
*/	int start=0;int time=0;queue<int>q[101];while(start<sub){	for(int i=1;i<=k;i++){	if(q[i].size()==0)continue;int y=q[i].front();array[y].pt--;//cout<<y<<" "<<pt[y]<<" "<<(pt[y]==0)<<endl;//cout<<array[y].pt<<endl;if(array[y].pt<=0){	q[i].pop();}}for(int i=1;i<=k;i++){if(q[i].size()==0){	if(array[start].st<time){q[i].push(start);array[start].end=time;//cout<<array[j].st<<" "<<time<<endl;start++;}elsebreak;}}time++;}//cout<<pt[7]<<" "<<a[7]<<endl;double sum=0;for(int i=0;i<sub;i++){	//cout<<array[i].end<<" "<<array[i].st<<endl;sum+=array[i].end-array[i].st;}if(sub==0)cout<<"0.0";elseprintf("%.1f",sum/(1.0*60)/(1.0*sub)); return 0;
}