TA的每日心情 | 鬱悶 2015-5-15 22:38 |
---|
簽到天數: 33 天 [LV.5]常住居民I
版主
TFcis - 105 附設監工官
- 積分
- 766
|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
本帖最後由 jd3 於 2014-11-13 00:32 編輯
這題真的很折磨人...
首先呢~ 又是個題意釐清
題意釐清
雖然是環狀的, 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
|
|