切換
舊版
前往
大廳
主題

ZeroJudge - c086: 00402 - M*A*S*H 解題心得

Not In My Back Yard | 2020-09-03 00:00:27 | 巴幣 0 | 人氣 183

題目連結:


題目大意:
輸入有多列,每列給定 22 個正整數。第一個整數 N 以及第二個整數 X (1 ≦ X ≦ N ≦ 50),代表有 N 個人參加樂透,並且從中選出 X 個人(所有人排成一列,編號為 1 ~ N)。剩下的 20 個正整數,代表每一張撲克牌的值(皆介於 1 ~ 13 之間)。

樂透的玩法如下:
對於每張撲克牌的值 K,從第 1 個人開始數,數到第 K 個人時淘汰該人;接著從被淘汰的那個人的下一個人開始數,一樣數 K 個。重複此步驟直到隊伍的結尾。

剩下的人作為新的隊伍繼續到下一張撲克牌。直到淘汰了 N - X 人為止。輸出剩下的那 X 個人一開始在隊伍中的編號。如果 20 張撲克牌跑完後,剩下的人還大於 X ,則輸出剩下的人一開始的編號。

輸出時,對於每列(即每筆測試資料)先輸出「Selection #」並接著一個整數,代表這是第幾筆測資。接著的一列即是剩下的人之編號,兩兩個數字之間用一空白隔開(結尾不能有多餘的空白,在 ZeroJudge 上沒關係,但是在 UVa 原題就有關係)。然後每筆測資的輸出之後,多空一個空白列。參見範例輸出。



範例輸入:
10 2 3 5 4 3 2 9 6 10 10 6 2 6 7 3 4 7 4 5 3 2
47 6 11 2 7 3 4 8 5 10 7 8 3 7 4 2 3 9 10 2 5 3
-
範例輸出:
Selection #1
1 8
 
Selection #2
1 3 16 23 31 47



解題思維:
就是單純地模擬。可以不用將每一張撲克牌之後挑選出來的人之編號放到新的陣列作為新隊伍,只需要一個布林陣列用來儲存對應編號的人是否被淘汰了。如果在數 K 個人的過程中,目前第 i 個人早已被淘汰,則跳過即可不須納入 K 個人的計數之中。

並用一個整數變數計算目前沒被淘汰的人(即剩下的人),一旦該數字 ≦ X ,就可以不用看剩下的撲克牌了(當前撲克牌也不需要繼續)。

最後,不管 20 張撲克牌有沒有被用完,也不管剩下多少個人,就是利用布林陣列儲存的值,哪個人沒被淘汰就輸出該編號即可。




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

創作回應

相關創作

更多創作