4 - 串珠珠問題

jd3

這題真的很折磨人...


首先呢~ 又是個題意釐清
題意釐清
雖然是環狀的， 1~n可以跨過兩端不過就如圖上畫的一樣
排完最後才接上去
所以首尾不能交換




解法
首先要有「逆序數對」的概念這題就是泡沫排序交換次數的題目，加上了最後可以首尾相接的條件

以範測為例
3 5 4 2 1

因為可首尾相接
答案會是排成下列5種之中，逆序數對最少的
1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
3 4 5 1 2
2 3 4 5 1


利用 BIT 或 merge sort
可以 O( N*log(N) ) 找出其中一組

關鍵問題在「如何用已知的一組答案算出下一組」
試著找看看轉移到相鄰一組的方法 ( 只要能轉到隔壁，自然能轉到隔壁的隔壁 )
1 2 3 4 5
如果把 5 搬到最前面變成：
5 1 2 3 4


前後的差異我們從逆序數對的數量分析比較一下前後兩組的關係

原序：3 5 4 2 1

目標：1 2 3 4 5
          5 1 2 3 4

如果說我們找逆序數對的方法是
對於每一個元素找前面(左)有幾個數字比它大，最後加總
那麼換到第2組的影響是?

可以把第2組想像成是這樣

原序：3 0 4 2 1
目標：0 1 2 3 4




轉換寫起來像這樣
原本數列：3 5 4 2 1
逆序數對：0 0 1 3 4

原本數列：3 0 4 2 1
逆序數對：0 1 0 2 3


原本最大的數字 : 5
變成 0 之後，它原本位置的右側每個元素找到的逆序數對數量 會 -1
而 0 這個元素往左看每個元素都比較大，相較於原本找到的 0 個會 +左側元素數量


如果12345這組找到的逆序數對數量是K (範測 = 8)
所以轉到 51234 這組就是 K - (5-2) + (2-1)
(5是N 也就是最右端 , 2是數字5原本的位置, 1是最左端位置)


接下來因為4變成最大的數字
直接比照辦理
依此類推


如果你這樣寫完還是沒AC的話...


記得開long long