主題

ZeroJudge - e001: 9608 連的士兵 解題心得

Not In My Back Yard | 2021-02-01 00:00:03 | 巴幣 0 | 人氣 35

題目連結:


題目大意:
輸入第一列給定兩正整數 n 、 q (0 < n ≦ 300000 , q = n - 2),代表有 n 位士兵(按照輸入順序編號為 1 ~ n)以及 q 次的叫號。接著第二列給定 n 個正整數 h(1 ≦ h ≦ 10 ^ 7),代表這 n 位士兵的身高(保證所有人身高不一樣)。最後有 q 列,每列給定一正整數,代表長官叫的編號。

士兵們會先按身高由小排到大(小的在左、大的在右),接著長官每叫一個士兵的編號,該士兵就要回答其左右的士兵之編號並離開隊伍(隊伍最左以及最右不會被叫到,而且同一個編號不會被叫第二次)。

因此輸出會有 q 列,每列為兩正整數,代表被叫到的士兵當前的左右士兵之編號。輸出格式參見範例輸出。



範例輸入:
10 8
45 93 86 20 32 75 48 90 79 36
7
3
8
5
6
10
9
1


範例輸出:
1 6
9 8
9 2
4 10
1 9
4 1
1 2
4 2


解題思維:
首先將所有士兵的身高與其編號用一結構(Struct)存在一起。然後將其按照身高由小排到大,接著用一個陣列 M[i],儲存編號 i 的士兵現在於排序後的第幾個位置(因為我們將是對這個排序後隊伍做操作)。

結構裡除了有身高以及編號以外,還有兩個指標用以指向其在隊伍裡左邊以及右邊的士兵。因此排序完後,我們還需要設定每一位士兵的左邊以及右邊之指標。

接著對於每個叫號(以 Q 表示),我們可以先用 M[Q] 找到士兵在隊伍中的位置,然後輸出其左與右的士兵之編號。接著因為該名士兵要離開隊伍,所以將其左邊士兵負責指向右邊的指標指向自己的右邊、右邊士兵負責指向左邊的指標指向自己的左邊,接著便可以離開隊伍(因為不會被叫到第二次,所以可以不用真的做出「離開」的動作)。

q 次的叫號都執行完後,輸出的內容即是所求。




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

創作回應

胖胖貓
其實這一題指標的部份可以透過DSU「連通」的概念找到最左邊和最右邊的士兵編號,每當這個士兵被出列後就把自己編號指向最左和最右邊還在隊伍內的士兵:類似 a567的死線排程要找到"有空的前一天"。
https://www.codepile.net/pile/l9Eya79p
2021-02-01 02:27:24

更多創作