切換
舊版
前往
大廳
主題

ZeroJudge - b938: kevin 愛殺殺 解題心得

Not In My Back Yard | 2019-08-30 22:09:33 | 巴幣 0 | 人氣 433

題目連結:


題目大意:
第一列給定兩正整數 n 、 m (1 ≦ n 、 m ≦ 10 ^ 6),代表有 n 個人站成一列,編號為 1 ~ n 。接著的第二列有 m 個正整數 k (1 ≦ k ≦ n),代表要除掉站在編號為 k 的後面那個人(一開始是編號 k + 1 站在編號 k 的後面)

請輸出每個被除掉的人之編號。除非編號 k 已死或是編號 k 為目前隊列的最後一個人(沒有後面的人),此時請輸出「0u0 ...... ?」。



範例輸入:
5 4
1 1 5 4


範例輸出:
2
3
0u0 ...... ?
5


解題思維:
用一個陣列紀錄編號 i 的人後面是誰。(一開始為 i + 1。除了最後一個人,設為 -1 以表示後面沒人)再宣告一布林陣列代表編號 i 的人是否死亡。(一開始大家皆存活,因此都設 false)

接著每遇到要殺掉編號 k 後面的人時,先判斷編號 k 是否死亡(用上面的布林陣列)或是編號 k 後面沒人(後面的人為「-1」,代表後面沒人)。若有符合任何一個條件代表要輸出「0u0 ...... ?」;兩者皆非的話,才殺掉編號 k 後面的人。除掉之後,現在站在編號 k 後面的人是原本站在後面(被除掉的那個人)的後面那個人。

如上去更新陣列,即可得到所求。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作