題目連結:
題目大意:
輸入第一列給定兩正整數 N 、 K(1 ≦ N 、 K ≦ 10 ^ 6),代表有 N 個人要約會而本體加上分身後有 K 位士道。接著第二列給定 N 個非負整數 T,代表每個人所需的約會時間。
現在士道們會「依序」和每個人約會(一個人只會分配到一個士道,且約會時間必須完整不中斷),當有士道先行結束約會便可以直接繼續與下一個人約會。試問與所有人約會完最少所需時間為何?
範例輸入:
範例輸入 #1
3 2
3 5 2
範例輸入 #2
3 1
1 2 3
範例輸入 #3
3 5
1 3 7
範例輸出:
範例輸出 #1
5
範例輸出 #2
6
範例輸出 #3
7
解題思維:
利用時間戳記(Time Stamp)搭配優先佇列(Priority Queue)即可模擬出來。
先將前 K 個人(如果有的話)各自分配一個士道給她們,並且將這些人各自所需約會時間放進優先佇列裡作為最一開始的時間戳記。
接著重複以下步驟直到佇列為空為止:
從優先佇列中取出時間戳記之值最小的,其代表著這是目前會最早結束約會的士道。因此他可以被分配給下一個還沒約到會的人(如果還有的話),因此我們可以將該士道結束約會時的時間 T 加上下一個人所需的約會時間而得到約會結束的時間,而此即為「時間戳記」。將該時間戳記重新丟回優先佇列即可。
而上述過程中的最後一個被取出的士道,該時間戳記即為所求最少所需時間。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。