前往
大廳
主題

ZeroJudge - d166: 反轉表 解題心得

Not In My Back Yard | 2021-04-24 00:00:13 | 巴幣 0 | 人氣 444

題目連結:


題目大意:
對於一個為數字 1 ~ m 這 m 個數字的一種排列之數列 A1 、 A2 、 …… 、 Am,其反轉表 B1 、 B2 、 …… 、 Bm 的項次 Bi 定義為:在數列 A 裡,排在數字 i 前面(假設數字 i 為 Aj,則為 A1 ~ Aj-1)有多少數字比它大。

現在輸入有多列,每列給定若干個數字(以一列只含 -1 的輸入作結),代表著一個數列之反轉表。試問原數列 A 為何?



範例輸入:
2 3 6 4 0 2 2 1 0

-1


範例輸出:
5 9 1 8 2 6 4 7 3


解題思維:
首先因為輸入的格式有點神祕(可以從範例輸入看到),所以我們需要一列一列讀,然後看該列輸入有沒有數字。有的話就將那些數字擷取出來。如果只擷取出一個 -1 ,則代表輸入結束。

然後根據題意 B1 代表著數字 1 (1 不一定在 A1 喔)前面的數字有 B1 個大於它。而其他項次也是則同理。

因此,我們可以藉由暴力法去搜尋每個數字應放在哪。以範例輸入 2 3 6 4 0 2 2 1 0 為例:
一開始數列 A 預設為空,如下
_ _ _ _ _ _ _ _ _
有 9 個格子(因為範例有 9 個數字)

2 3 6 4 0 2 2 1 0
2 代表著數字 1 前面有 2 個數字比它大,所以
_ _ 1 _ _ _ _ _ _

2 3 6 4 0 2 2 1 0
3 代表著數字 2 前面有 3 個數字比它大,所以
_ _ 1 _ 2 _ _ _ _
(基本上就是數空格的數量,因為接下來搜尋的數字一定比 2 大。所以 2 現在放的位置前面有 3 個空格,因而放在那裡)

2 3 6 4 0 2 2 1 0
6 代表著數字 3 前面有 6 個數字比它大,所以
_ _ 1 _ 2 _ _ _ 3

2 3 6 4 0 2 2 1 0
4 代表著數字 4 前面有 4 個數字比它大,所以
_ _ 1 _ 2 _ 4 _ 3

2 3 6 4 0 2 2 1 0
0 代表著數字 5 前面有 0 個數字比它大,所以
5 _ 1 _ 2 _ 4 _ 3

2 3 6 4 0 2 2 1 0
2 代表著數字 6 前面有 2 個數字比它大,所以
5 _ 1 _ 2 6 4 _ 3

2 3 6 4 0 2 2 1 0
2 代表著數字 7 前面有 2 個數字比它大,所以
5 _ 1 _ 2 6 4 7 3

2 3 6 4 0 2 2 1 0
1 代表著數字 8 前面有 1 個數字比它大,所以
5 _ 1 8 2 6 4 7 3

2 3 6 4 0 2 2 1 0
0 代表著數字 9 前面有 0 個數字比它大,所以
5 9 1 8 2 6 4 7 3

因此所求數列 A 為 5 9 1 8 2 6 4 7 3。而其他的情況也可以按照類似以上之步驟推出所求。




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

創作回應

更多創作