首页 > 代码库 > HDU 4884 模拟炒饭

HDU 4884 模拟炒饭

题意 :一个人开了一家炒饭馆,炒饭原则是这样的,一次最多炒K个相同种类的炒饭,消耗T单位的时间。优先按队伍中的顺序处理,如果在我刚准备炒这一锅饭的时候或之前,你来这定饭,我可以帮你炒,否则在我炒的时候不准接单。也就是每次炒饭尽量多炒,但是不准多余,输入每个人来的时间,所需饭的种类以及个数,一次输出每个人离开的时间。

题解 : 弄懂题意是重点 

             

举个例子,比如每次可以炒5份,每次5分钟。

第一个顾客08:00进来,点了2份A,

第二个顾客08:04进来,点了3份A。

在08:00开始炒的话,由于这个时候第二个顾客还没进来,所以就只炒2份,第一个顾客在08:05离开,这时才炒第二个的3份,所以第二个离开时间是08:10。

同样是每次可以炒5份,每次5分钟。

第一个顾客08:00进来,点了6份A,

第二个顾客08:01进来,点了5份B,

第三个顾客08:02进来,点了4份A。

同样地,先炒5份给第一个,还差一份,这是已经是08:05了,第三个顾客也进来了,所以这时直接炒5份A(因为会尽可能多地炒),08:10第一个和第三个可以同时离开。接着才炒第二个的。

我的解法是从第一份饭开始考虑,如果我多炒且后面的人能接受的话就给你,你的需求就减少我多炒的份数,注意更新锅子在用的时间,以及最后时间可能超过24小时,从0开始重新记。

代码:

#include<stdio.h>
#include<string.h>
struct co
{
   int t,now,flag;        
}cun[1005];
int mark[1005];
int maxx ( int a, int b )
{
   if(a > b)  return a;
   return b;    
}
int main()
{
  int T, n, t, k, m, hour, minn, x, num, flag = 0;
  scanf("%d",&T);
  while(T--)
  {
    memset(cun,0,sizeof(cun));
    memset(mark,0,sizeof(mark));
    if(flag)  printf("\n");
    flag=1; 
    scanf("%d %d %d %d", &n, &t, &k, &m);
    for(int i = 1; i <= m; i++)
    {
      scanf("%d:%d %d %d", &hour, &minn, &x, &num);
      cun[i].t = hour*60 + minn;
      cun[i].now = num;
      cun[i].flag = x;
    }       
    int max = 0;   
    for(int i = 1; i <= m; i++)
    { 
      if(!cun[i].now)  continue;
      cun[i].t = maxx( max, cun[i].t );
      while(cun[i].now > 0)
      {
        cun[i].now -= k;
        cun[i].t += t;                
      }      
     
      if(cun[i].now < 0)
      {
         int j = i + 1;
         cun[i].now = -cun[i].now;
         while((cun[j].t <= cun[i].t - t)&&cun[i].now!=0 && j <= m) 
         { 
           if(cun[j].flag != cun[i]. flag) { j++; continue;}
           if(cun[j].now <= cun[i].now)     
           {
             mark[j] = cun[i].t;      
             cun[i].now -= cun[j].now;  
             cun[j].now = 0;    
           }      
           else
           { 
             cun[j].now -= cun[i].now;
             cun[i].now = 0;               
           }         
           j++;       
         }  
      }
      mark[i] = cun[i].t;
      max = maxx(cun[i].t,max); 
    }
    for(int i = 1; i <= m; i++)
    {
      int hh = mark[i] / 60;
      int mm = mark[i] % 60;
      hh %= 24;
      printf("%02d:%02d\n",hh,mm);         
    }
  }    
}

HDU 4884 模拟炒饭