題意:

三種洗漱房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);    }}