有一銀行業務的申請包括了 K 個步驟,且需依序進行才可以完成。 K 個步驟中的每個步驟由一個櫃檯人員負責處理。
同一櫃檯同時只能服務一人,一旦開始服務某人,就必須繼續服務到這位申請人的步驟全部完成才可以換下一位。
然而,每個申請人會因 個 人情況不同,在每個步驟都可能需要不同的處理時間。
若有 N 個申請人排隊,他們必須依序完成 K 個步驟,且不可插隊或中途離開。
輸入每個人於每個步驟所需要的處理時間,請輸出完成全部的申請服務需要花多少時間;
也就是從第一個人開始接受服務,到最後一位完成最後步驟,總共需要多少時間。
例如:有三個人排隊,服務包含四個步驟。第一個人 A 於各個步驟所需的處理時間依序為 7 3 5 8 分鐘。]
第二個人 B 於各個步驟所需的處理時間依序為 1 6 4 5 分鐘。第三個人 C 於各個步驟所需的處理時間依序為 6 2 7 3 分鐘。
一開始,只有第一個客戶 A 可以到第一櫃檯處理,需要 7 分鐘的服務時間。請參考下表。
第 8 分鐘開始時,第一個客戶 A 前進到第二櫃檯,需要 3 分鐘。而同時,第二個客戶 B 可以到第一櫃檯,需要 1 分鐘。
雖然第 8 分鐘結束時,第二個客戶 B 已經完成於第一櫃檯的服務,但是因為第一個客戶 A 仍在第二櫃檯接受服務,
所以第二個客戶 B 必須於第二櫃檯前排隊,一直等到第 11 分鐘開始時,才可以接受第二櫃檯的服務,
因為第一個客戶 A 在第二櫃檯,需要 3 分鐘的服務。
下表列出每個客戶在每個櫃檯接受服務的時間對應關係。
注意:在第 16 分鐘時,第三櫃台是空閒的,原因是因為雖然A已經於第 15 分鐘完成在第三櫃台的服務,但是 B 卻必須在第 16 分鐘時停
留在第二櫃檯繼續接受完服務。
在此範例中,總共的服務時間是 31 分鐘。
第一行:N K ,其中 N 表示多少人, K 表示多少步驟
第二行:K 個數字,代表第一個人依序於各步驟所需的處理時間,兩時間以空白 分隔
第三行:K 個數字,代表第二個人依序於各步驟所需的處理時間,兩時間以空白 分隔
:
第N+1 行: K 個數字,代表第 N 個人依序於各步驟所需的處理時間,兩時間以空白 分隔
總共的服務時間
3 4 7 3 5 8 1 6 4 5 6 2 7 3
31
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |