首页 > 代码库 > 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 模拟炒饭