[ACM] HDU 4884 TIANKENG’s rice shop (模拟）

TIANKENG’s rice shop

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
        

Source

BestCoder Round #2  

Recommend

liuyiding

解題思路：

這道模拟題太坑了......

一共有n種炒飯，每種炒飯炒一次都花t分鐘，炒一次是k份的量，每次隻能炒同一種炒飯，有m個客人，給出每個客人的到來時間，以及所要炒飯的種類和數量，問每個客人的最早離開時間.

一開始第三組測試資料沒看懂

n=2 t=5 k=4 m=2

08：00 1 1

08：04 1 1

第一位客人8點的時候要了第一種炒飯1分，第二位客人8點04的時候要了第1種炒飯1份，那直接炒4份不就可以了嗎...兩位客人都是0點5分離開，坑啊，不能這樣，正确的應該是這樣聯系實際，首先來的是第一位客人要了第一種炒飯1份，那麼就得花5分鐘就隻炒1份，雖然這5分鐘内有第二位客人來了，但是不能給他炒，等第一位客人走了以後，再給第二位客人來炒。

還有另外種情況，後面的可以加在前面炒

還是前面的資料，隻不過客人的資訊該為了

08:00 1 6

08:02 2 1

08:03 1 X

首先第一位客人，要了6份，因為一次最多炒4份，是以第一份炒完4份後，時間為8點05，這時候第二位和第三位都來了，正好第三位和第一位要的是一樣的，那麼下一次再為第一位客人炒飯（因為還差2份）時，就可以順便為第三位客人也炒出來，如果X=2的話，那麼最後一次為第一位客人炒飯，2份給它，2份給第三位個人就可以了，兩位客人同時離開，如果X<2的話，假設為1，那麼最後一次隻要炒3份就可以了。如果X>2的話，那麼炒出來2分給第三位客人留着，到了他的時候，再給他炒X-2份就夠了.

寫這道題，頭暈暈的......

代碼：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <cmath>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cctype>
using namespace std;
#define ll long long
const int maxn=1002;//最大種類數
int n,t,K,M;//n為種類數,t為一次炒飯的時間，k為一次可以炒多少份，m是有m個客人
bool done[maxn];

struct Customer
{
    int h,m;
    int time;
    int kind;
    int num;
    int ans;
}cus[maxn];

void output(int t)
{
    int h=t/60;
    h%=24;
    int m=t%60;
    if(h<=9)
        printf("0%d:",h);
    else
        printf("%d:",h);
    if(m<=9)
        printf("0%d\n",m);
    else
        printf("%d\n",m);
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&n,&t,&K,&M);
        memset(done,0,sizeof(done));
        for(int i=1;i<=M;i++)
        {
            scanf("%d:%d %d %d",&cus[i].h,&cus[i].m,&cus[i].kind,&cus[i].num);
            cus[i].time=cus[i].h*60+cus[i].m;
        }
        int curtime=-1;//目前時間
        for(int i=1;i<=M;i++)
        {
            if(done[i])
                continue;
            if(cus[i].time>=curtime)
                curtime=cus[i].time;

            int c=(cus[i].num)/K;//為第i個顧客需要炒幾次飯
            if(cus[i].num%K!=0)
                c++;
            //cout<<"tt"<<tt<<endl;
            cus[i].ans=curtime+c*t;//第i個顧客離開時間
            //int curt=curtime+cus[k].num/K*t;
            int curt=cus[i].ans-t;//為第i個顧客最後一次炒飯開始的時間，
            //因為這時候要看看後面的顧客有沒有和目前顧客要的一樣的，順帶着“炒出來一部分”

            curtime=cus[i].ans;
            int left=c*K-cus[i].num;//最後一次可以多炒一部分，比如每次炒4份，目前顧客要10份，那麼得炒3次，第三次炒可以炒4份，那麼就會多出來2份

            done[i]=1;
           // cout<<"kk"<<k<<"left"<<left<<endl;
            for(int j=i+1;j<=M;j++)
            {
                if(cus[j].time>curt)
                    break;
                if(cus[j].kind!=cus[i].kind)
                    continue;
                if(left>=cus[j].num)//目前顧客多出的飯可以直接給後面需要的
                {
                   // cout<<"inininininin"<<endl;
                    cus[j].ans=cus[i].ans;
                    done[j]=1;
                    left-=cus[j].num;
                }
                else
                {
                    cus[j].num-=left;
                    left=0;
                    break;
                }

            }
            //kindn[cus[k].kind]+=left;
            //cout<<cus[k].kind<<"  sssssssss   "<<left<<endl;
        }
        for(int i=1;i<=M;i++)
            output(cus[i].ans);
        if(T)
        printf("\n");
    }
    return 0;
}