HDU-4884-TIANKENG’s rice shop【模拟】

---

HDU-4884-TIANKENG’s rice shop

---

        Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

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

题目链接：HDU-4884

题目大意：这个人能在t时间内炒k碗相同的饭。饭的种类有1-n种。有m个人来买饭，问最快的时间

题目思路：直接模拟，需要考虑的是，如：

    这个人能在5分钟内炒4碗饭。

    A： 在8:00分要了3份2号饭。   B： 在8:01分要了1份1号饭。   C： 在8:02分要了1份1号饭。

    --->B和C的饭可同时炒

另外有个坑点，24:04要转化成00:04。

以下是代码：

#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;
int last_time[1005];  //用于记录最后一次炒i号炒饭的时间
int last_cnt[1005];   //用于记录最后一次炒i份饭还剩下多少份
int lim = 24 * 60;
void print(int time)
{
    if (time >= lim) time %= lim;   //注意时间的转化
    int hour = time / 60;
    int mins = time % 60;
    printf("%02d:%02d\n",hour,mins);
}
int main(){
    int T;
    cin >> T;
    while(T--)
    {
        int n,t,k,m;
        memset(last_time,0,sizeof(last_time));
        memset(last_cnt,0,sizeof(last_cnt));
        scanf("%d%d%d%d",&n,&t,&k,&m);
        int finish = 0;
        for (int i = 0; i < m; i++)
        {
            int h,mins,id,num;
            scanf("%d:%d %d%d",&h,&mins,&id,&num);
            int time = h * 60 + mins;  //便于计算
            if (time <= last_time[id] && num <= last_cnt[id])   //如果当前时间＜最后一次炒饭的时间并且能直接炒完
            {
                last_cnt[id] -= num;  
                print(last_time[id] + t);  //输出上一次炒饭时间 + 炒饭需要的时间
                continue;
            }
            else if (time <= last_time[id] && last_cnt[id]) //如果当前时间＜最后一次炒饭的时间但是不能直接炒完（先把能炒的提前炒掉，剩余部分轮到的时候再炒）
            {
                num -= last_cnt[id];
            }
            int need = (num / k + (num % k ? 1 : 0)) * t;  //炒完需要的时间
            finish = max(finish,time) + need;  //判断到达的时间和排队的时间（上一个人完成的时间） + 炒饭需要的时间 = 这个人完成的时间
            print(finish);
            last_cnt[id] = need / t  * k - num;
            last_time[id] = finish - t;  //最后一次炒饭开始的时间
        }
        if (T) puts("");
    } 
    return 0;
}