首页 > 代码库 > hdu4884 TIANKENG’s rice shop【模拟】

hdu4884 TIANKENG’s rice shop【模拟】

2024-08-04 00:52:16   225人阅读

TIANKENG’s rice shop

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 345    Accepted Submission(s): 71


Problem Description
TIANKENG managers a pan fried rice shop. There are n kinds of fried rice numbered 1-n. TIANKENG will spend t time for once frying. Because the pan is so small, TIANKENG can fry k bowls of fried rice with same kind at most. Assuming that there are m customers coming to the shop, and we know the arriving time of each customer and the brand and number of the fried rice they need. Could you tell TIANKENG the departure time of every customer respectively? Pay attention that TIANKNEG will serve the customer who comes earlier and he will fry the rice as much as possible. Meanwhile, customers are in queue depending on their arriving time(the earlier they arrive, the more front they stand).
 

Input
The first line contains a positive integer T(T<=100), referring to T test cases.
For each test case, the first line has 4 positive integer n(1<=n<=1000), t(1<=t<=10), k(1<=k<=5), m(1<=m<=1000), then following m lines , each line has a time(the time format is hh:mm, 0<=hh<=23, 0<=mm<=59) and two positive integer id(1<=id<=n), num(1<=num<=10), which means the brand number of the fried rice and the number of the fried rice the customer needs.
Pay attention that two or more customers will not come to the shop at the same time, the arriving time of the customer will be ordered by the time(from early time to late time)
 

Output
For each test case print m lines, each line contains a time referring to the departure time of the customer. There is a blank line between two test cases.
 

Sample Input
3
2 1 4 2
08:00 1 5
09:00 2 1
2 5 4 3
08:00 1 4
08:01 2 2
08:02 2 2
2 5 4 2
08:00 1 1
08:04 1 1
 

Sample Output
08:02
09:01

08:05
08:10
08:10

08:05
08:10
分析：普通模拟，卡了一天。
代码示例：
#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#define Max(a,b) a>b?a:busing namespace std;typedef struct{    int time,id,num;}node;typedef struct{    int time,s,t,id;}nodf;node E[2000+10];int Time[2000+10];int main(){    int T,n,t,k,m;    int a,b,c,d;    scanf("%d",&T);    while(T--)    {        scanf("%d%d%d%d",&n,&t,&k,&m);        for(int i=0;i<m;i++)        {            scanf("%d:%d%d%d",&a,&b,&c,&d);            E[i].time=a*60+b,E[i].id=c,E[i].num=d;            Time[i]=-1;        }        nodf sum;        sum.time=-1;        for(int i=0;i<m;i++)        {            if(Time[i]!=-1)            continue;            sum.time=Max(sum.time,E[i].time);            sum.s=sum.t=0,sum.id=E[i].id;            while(sum.s<E[i].num)            {                sum.s+=k;                sum.t+=t;            }            Time[i]=sum.time+sum.t;            sum.time+=(sum.t-t),sum.s-=E[i].num;            int j=i+1;            while(E[j].time<=sum.time&&sum.s>0&&j<m)            {                if(E[j].num>sum.s&&E[j].id==sum.id)                {                    E[j].num-=sum.s;                    sum.s=0;                }                if(E[j].num<=sum.s&&E[j].id==sum.id)                {                    sum.s-=E[j].num;                    Time[j]=sum.time+t;                }                j++;            }            sum.time+=t;        }        for(int i=0;i<m;i++)        {               a=Time[i]/60,b=Time[i]%60;            a%=24;            printf("%02d:%02d\n",a,b);        }        if(T>0)        printf("\n");}return 0;}                     

hdu4884 TIANKENG’s rice shop【模拟】


联系
我们