九度互动社区IT名企招聘上机考试热身赛

http://ac.jobdu.com/problem.php?pid=1326 Waiting in Line

//简单模拟题
#include<iostream>
#include<cstdio>
using namespace std;
#include<memory.h>

int pt[1001],leave[1001],start[21];
int n,m,k,q;
inline bool scan_d(int &num)  //  这个就是 加速的 关键了   
{
	char in;bool IsN=false;
	in=getchar();
	if(in==EOF)
		return false;
	while(in!='-'&&(in<'0'||in>'9')) in=getchar();
	if(in=='-')   { IsN=true;num=0;}
	else num=in-'0';
	while(in=getchar(),in>='0'&&in<='9')
	{
		num*=10,num+=in-'0';
	}
	if(IsN)
		num=-num;
	return true;
}

void solve()
{
	int i,j,index,t,p,count=k;
	int num[21],window[21][13];
	memset(start,0,sizeof(start));
	memset(num,0,sizeof(num));
	j = index = 1;
	for(i = 1 ; i <= n*m && i <= k ; ++i)    //刚开始时，n个窗口都是空的，客户依次选择队伍最短的窗口
	{
		window[j][index] = i;
		num[j]++;
		j++;
		if(j>n)
		{
			j = 1;
			++index;
		}
	}
	j = i;   //刚开始的n个窗口已经都排满了客户
	t = 0;
	while(t <= 540)
	{
		++t;
		for(i = 1 ; i <= n ; ++i)
		{
			if(num[i] > 0 && pt[ window[i][1] ] == t - start[i])
			{
				leave[ window[i][1] ] = t;
				start[i] = t;
				--count;        //一个用户离开
				for(p = 2 ; p <= num[i] ; ++p)
					window[i][p-1] = window[i][p];    //每个窗口的第一个用户离开后，后面的客户依次往前移动
				--num[i];
				if(j <= k)    //还有等待的客户的时候，往窗口中再增加一个
				{
					window[i][p-1] = j;
					++num[i];
					++j;
				}
			}//if
		}//for
		if(!count)    //所有客户都处理完的时候，直接退出
			break;
	}
}

int main(void)
{
	int i,j;
	while(scanf("%d %d %d %d",&n,&m,&k,&q)!=EOF)
	{
		memset(leave,1,sizeof(leave));
		for(i = 1 ; i <= k ; ++i)
			scan_d(pt[i]);
		solve();
		for(i = 0 ; i < q ; ++i)
		{
			scan_d(j);
			if(leave[j] > 540)
				puts("Sorry");
			else
				printf("%02d:%02d\n",leave[j]/60+8,leave[j]%60);
		}
	}
	return 0;
}