PAT 1014 Waiting in Line (30分) 一个简单的思路

这题写了有一点时间，最开始想着优化一下时间，用优先队列去做，但是发现有锅，因为忽略了队的长度。

然后思考过后，觉得用时间线来模拟最好做，先把窗口前的队列填满，这样保证了队列的长度是统一的，这样的话如果到某个时间，队首的人已经服务完了，这样这个队列的长度就减少一，这就变成了所有队列中长度最短的队列，所以直接向这个队列里面添加一个人就可以了。

按照从小到大轮询窗口的话，这样正好符合题中的要求，就是队列长度相同短，先选窗口序号小的窗口。如果按照这种策略，少一个就补一个的策略，队列长度会一直保持相等。

#include <bits/stdc++.h>

using namespace std;

const int maxn=1010;

int ans[maxn],a[maxn],N,M,K,Q,t[maxn];

queue<int> q[22];

int pret[22];

void print(int t)

{

	if (t==-1) {

		printf("Sorry\n");

		return;

	}

	t+=480;

	int hh=t/60,mm=t%60;

	// printf("%d %d	",hh,mm);

	if (hh>17) {

		printf("Sorry\n");

	}

	else {

		printf("%02d:%02d\n",hh,mm);

	}

}

int main()

{

	// freopen("in.txt","r",stdin);

	scanf("%d%d%d%d",&N,&M,&K,&Q);

	for (int i=1;i<=K;i++) {

		scanf("%d",&t[i]);

	}

	for (int i=1;i<=Q;i++) {

		scanf("%d",&a[i]);

	}

	int c=1;

	for (int i=1;i<=M;i++) {

		for (int j=1;j<=N;j++) {

			q[j].push(c++);

			if (c>K) {

				break;

			}

		}

	}

	memset(ans,-1,sizeof(ans));

	for (int i=0;i<=540;i++) {

		if (c>K) break;

		for (int j=1;j<=N;j++) {

			int p=q[j].front();

			int tt=t[p];

			if (i-pret[j]==tt) {

				ans[p]=i;

				q[j].pop();

				q[j].push(c++);

				pret[j]=i;

				if (c>K) {

					goto outloop;

				}

			}

		}

	}

	outloop:

	for (int j=1;j<=N;j++) {

		while (!q[j].empty()) {

			if (pret[j]>=540) {

				break;

			}

			int p=q[j].front();

			ans[p]=pret[j]+t[p];

			pret[j]+=t[p];

			q[j].pop();

		}

	}

	for (int i=1;i<=Q;i++) {

		print(ans[a[i]]);

	}

	return 0;

}

巴特西

PAT 1014 Waiting in Line (30分) 一个简单的思路

最新文章

热门文章