首页 » C++ » PAT 1014. Waiting in Line (30)

PAT 1014. Waiting in Line (30)

原文 http://blog.csdn.net/changeforeve/article/details/76431325

2017-07-31 15:20:09阅读(632)

题目:1014.>1014. Waiting in Line (30)

思路:

           1.在黄线内,客户队列已定;

           2.在黄线外,根据各窗口目前服务的客户离开时间来选择队列。

注意:

           1.在17:00以前被服务(服务结束时间可以在17:00以后)的用户,输出时间,其他输出“Sorry";

           2.注意判断时间,有在17:00以前开始服务,17:00以后结束的,也有从8:00一直到17:00以后的,这些情况必须考虑。

代码:

#include<iostream>
#include<vector>
#include<iomanip>
using namespace std;
struct window
{
	vector<int> sum;        //目前该窗口排队时间
	vector<int> q;          //在该窗口排队的顾客
};
int main()
{
	int N,M,K,Q;
	cin>>N>>M>>K>>Q;
	int win[1000]={0};      //客户对应的窗口
	int customer[1000]={0}; //客户等待时间
	int i,k;
	for(i=0;i<K;++i)
	{
		cin>>customer[i];   //标号全部减1,输入各客户的服务时间
	}
	vector<int> query(Q);       //询问队列
	for(i=0;i<Q;++i)
	{
		cin>>k;
		query[i]=k-1;       //统一起见,标号全部减1
	}
	vector<window> W(N);    //N个窗口
	int j;
	//黄线内客户
	k=0;
	for(i=0;i<M;++i)        //每一行
	{
		for(j=0;j<N;++j)    //每一个窗口
		{
			if(k<K)         //判断是否全部输入
			{
			if(i==0)        //对于第一行客户
				W[j].sum.push_back(customer[k]);     //初始情况
			else
				W[j].sum.push_back(W[j].sum[i-1]+customer[k]);
			W[j].q.push_back(k);//输入客户编号
			win[k]=j;           //客户所在窗口
			++k;
			}
			else
			    break;
		}
		if(k>=K)
			break;
	}
	
	//黄线外的排队情况
	while(k<K)
	{
		int num=W[0].sum.size()-M;   //当前0号窗口黄线内出现空缺的编号		
		int minsum=W[0].sum[num];    //离开时间
		int min=0;                   //窗口编号
		for(i=1;i<N;++i)             //评价每一个窗口,选择最小值
		{
			num=W[i].sum.size()-M;   //i窗口即将离开的编号
			if(W[i].sum[num]<minsum) //同等时间,选取编号最小窗口
			{
				minsum=W[i].sum[num];
				min=i;
			}
		}
		W[min].q.push_back(k);       //将该客户排入队列
		num=W[min].sum.size();
		W[min].sum.push_back(W[min].sum[num-1]+customer[k]);
		win[k]=min;                  //记录该客户所在窗口
		++k;
	}
	//查找
	int time;
	int t;
	int hour,minute;
	for(i=0;i<Q;++i)
	{
		j=query[i];      //客户编号
		k=win[j];        //当前所在窗口
		t=0;
		while(W[k].q[t]!=j && t<W[k].q.size()) //找到客户所在位置
		{		
			++t;
		}
		time=W[k].sum[t];
		hour=time/60+8;
		minute=time%60;
		if(time<=540 || (t>0 && W[k].sum[t-1]<540) ||(t==0))
		{
			cout<<setw(2)<<setfill('0')<<hour<<':';
		    cout<<setw(2)<<setfill('0')<<minute<<endl;
		}
		else
			cout<<"Sorry"<<endl;
		
	}
	system("pause");
	return 0;
}


最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹