[HOJ] 321 - 看診問題

Problem : 321 - 看診問題

Problem：

現在有n 個病患收到了醫療中心的通知，. 每個人都收到了三種資訊：

　　• 每個人的號碼(依序由1, 2, ... , n 編號)
　　• 每個人應抵達醫療中心的時間點
　　• 一個關於他們檢查依序要去的房間編號順序列表

醫療中心的房間編號依序為1, 2, ... , m，而來到醫療中心做檢查的病患必須遵守下規則：

　　• 如果說病患應抵達醫療中心的時間為 t，那麼他會在時間 t 時抵達他的房間列表的第一間。
　　• 如果有多個病患同時抵達同個房間，他們會按照號碼由小到大排隊。若前面已有一個隊伍，則此時這個隊伍會接續在前一個隊伍後面。
　　• 如果說時間 t 時有隊伍在房間 x 前，隊伍中的第一個人將在時間t 進入房間做檢查，並且會在時間 t+1 時離開並（瞬間）移動至他房間列表中的下一個房間的隊伍裡。而隊伍中的下一個人將會於 t+1 的時間點進入房間x。
　　• 如果說病患在時間 t 進入房間 x 檢查，且這已經是他列表中的最後一個房間時，他將於 t+1 的時間點離開醫療中心。

你的任務是求出最後一個離開醫療中心的病患於何時離開。

Input：

第一行有兩個整數n,m，表示病患數目與醫療中心的房間數目。

接下來有n行，每行會是：t_i, k_i, g_i,1, g_i,2, ... ,g_i,ki，表示第i個病患應於時間t_i抵達醫療中心，房間列表共有k_i個，依序為g_i,1, g_i,2, ... ,g_i,ki，此行所有整數將以空白隔開。

限制：
1 ≤ n,m ≤ 1000
0 ≤ t_i ≤ 1000000
k_i > 0
1 ≤ g_i,j≤ m
k₁ + k₂ + ... + k_n ≤ 100000

Output：

輸出一個數字，表示最後一個離開醫療中心的病患於何時離開。

Sample Input：

5 3
1 3 3 2 1
0 7 2 3 1 1 1 1 2
2 1 1
1 2 3 3
4 3 1 1 1

Sample Output：

12

HINT：

Line 1：有5個人，醫院有3間診間
Line 2：編號1的人，在時間1來到醫院，依序要去3,2,1診間
Line 3：編號2的人，在時間0來到醫院，依序要去2,3,1,1,1,1,2診間
Line 4：編號3的人，在時間2來到醫院，依序要去1診間
Line 5：編號4的人，在時間1來到醫院，依序要去3,3診間
Line 6：編號5的人，在時間4來到醫院，依序要去1,1,1診間

----------------------------------------------------------------------------------------------------

#include<stdio.h>

#include<queue>

#include<algorithm>

using namespace std;

struct P{

    int siz,num;

    friend bool operator < (P a,P b){

        if(a.siz!=b.siz) return a.siz>b.siz;

        return a.num>b.num;

    }

}in,out;

priority_queue<P> que;

int arr[1005][1005],fnt[1005]={0};

int room[1005]={0},add[1005];

int main(){

    int t,n,m,i,j,p,cnt,ans=0,rm;

    scanf("%d%d",&n,&m);

    for(i=0;i<n;i++){

        scanf("%d",&in.siz);

        in.num=i;

        que.push(in);

        scanf("%d",&add[i]);

        for(j=0;j<add[i];j++)

            scanf("%d",&arr[i][j]);

    }

    while(que.size()){

        out=que.top();

        que.pop();

        p=out.num;

        cnt=arr[p][fnt[p]++];

        room[cnt]=max(room[cnt],out.siz)+1;

        out.siz=room[cnt];

        ans=max(ans,out.siz);

        if(fnt[p]!=add[p])

            que.push(out);

    }

    printf("%d\n",ans);

}