uva 7219 Problem on Group Trip (优先队列)

题意:

三种洗漱房s1,s2,s3,n个人,每个人按1到3的顺序排队等候洗漱,给出每人在这三个洗漱房需要多少时间洗漱,并且排队过程中,编号小的先洗漱,问需要多少时间所有人完成洗漱

解题思路:

用优先队列存储在3个房间的等候队列,如果洗漱完了,就加入到下一个队列,注意如果两个相邻队列队首的人同时完成洗漱,比如s1,s2房间两人同时,完成,就先让s1那人先进入s2房间排队,然后再s2队列中编号最小的人去洗漱. 代码写的有乱,写了一个多小时,最后差一秒,交上ac,qaq.

代码:

#include <bits/stdc++.h>using namespace std;const int maxn=105;struct p  {      int tim[4];           int x;      bool Operator <(const p &a)const      {          return a.x<x;      }  }now[4], b[maxn];int main(){    int t;    cin>>t;    int e=1;    while(t--)    {	int n;	scanf("%d", &n);	PRiority_queue<p>a[4];  	int i, j;	for(i=0; i<3; i++)	{	  now[i].tim[0]=now[i].tim[1]=now[i].tim[2]=0;	}	for(i=0; i<n; i++)	{	  scanf("%d %d %d", &b[i].tim[0], &b[i].tim[1], &b[i].tim[2]);	  b[i].x=i;	  if(b[i].tim[0]!=0)	  {	     a[0].push(b[i]); 	  }	  else if(b[i].tim[1]!=0)	  {	     a[1].push(b[i]);	  }	  else if(b[i].tim[2]!=0)a[2].push(b[i]);	}	int book[5];	memset(book, 0, sizeof(book));	int ans=0;	for(i=0; i<3; i++)	{	   if(!a[i].empty())	   {	     now[i]=a[i].top();	 //    printf("%d ", now[i].x);	     a[i].pop();	   }	}	printf("Case #%d: ", e++);        while(now[0].tim[0]!=0||now[1].tim[1]!=0|| now[2].tim[2]!=0)	{	    	int mi=104, x=0;		for(i=0; i<3; i++)	{	 if(now[i].tim[i]!=0)	 {		 if(now[i].tim[i]<mi)		 {			mi=now[i].tim[i];			x=i;		 }	 }	}	ans+=mi;		if(mi==0)break;		//printf("now");	memset(book, 0, sizeof(book));	for(i=0; i<3; i++)	{	  if(now[i].tim[i]>0)now[i].tim[i]-=mi, book[i]=1;	  	 // printf("%d ", now[i].tim[i]);	   	    if(now[i].tim[i]==0 && book[i]==1)	    if(i<2) 	    {		if(now[i].tim[i+1]!=0) a[i+1].push(now[i]);		else if(i==0 && now[i].tim[i+2]!=0)a[i+2].push(now[i]);			    }	}	for(i=0; i<3; i++)	{	  if(now[i].tim[i]==0)	  {	    if(!a[i].empty()) {		    now[i]=a[i].top();		    a[i].pop();	    }	  }	}	//printf("/n");	}	printf("%d/n", ans);    }}