題目連結:
第一列給定兩正整數 n 、 m (1 ≦ n 、 m ≦ 10 ^ 6),代表有 n 個人站成一列,編號為 1 ~ n 。接著的第二列有 m 個正整數 k (1 ≦ k ≦ n),代表要除掉站在編號為 k 的後面那個人(一開始是編號 k + 1 站在編號 k 的後面)
請輸出每個被除掉的人之編號。除非編號 k 已死或是編號 k 為目前隊列的最後一個人(沒有後面的人),此時請輸出「0u0 ...... ?」。
用一個陣列紀錄編號 i 的人後面是誰。(一開始為 i + 1。除了最後一個人,設為 -1 以表示後面沒人)再宣告一布林陣列代表編號 i 的人是否死亡。(一開始大家皆存活,因此都設 false)
接著每遇到要殺掉編號 k 後面的人時,先判斷編號 k 是否死亡(用上面的布林陣列)或是編號 k 後面沒人(後面的人為「-1」,代表後面沒人)。若有符合任何一個條件代表要輸出「0u0 ...... ?」;兩者皆非的話,才殺掉編號 k 後面的人。除掉之後,現在站在編號 k 後面的人是原本站在後面(被除掉的那個人)的後面那個人。
如上去更新陣列,即可得到所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。