Re: [問題]有限swap裡找出最大數值
看板Prob_Solve (計算數學 Problem Solving)作者tkcn (小安)時間14年前 (2010/06/27 22:00)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《colorflags ()》之銘言：
: 我google了很久 不太知道要用什麼關鍵字
: 所以想請大家指點一下
: 問題是給一串數字 在k次相鄰的swap裡面找出最大的數值
: swap只能和隔壁的數字交換
: ex. 1 2 3 4
: 一次swap 就會是 2 1 3 4
: 兩次swap 就是 3 1 2 4
這個數列內的數字會不會重複?
(1) 如果不會重複，greedy 即可:
找出前 k+1 個數字中最大的 (假設是第 i 個)，把他換到第一個 (需要 i-1 次 swap)
如果還有剩下交換次數 k2，就遞迴下去處理，把 2~k2 間最大的換到第二個，依此類推
(2) 如果會重複，直覺上我會想 branch & bound:
找出前 k+1 數字中最大的那幾個，把他們分別換到第一個，並繼續遞迴下去...
但是，仔細想想會發現，其實用第一個方法就足夠了。
(如果有多個最大值，選擇出現較前者)
先寫到這裡，剩下的讓大家先想想 :p
(其實是英德大戰要開始了 Orz)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.134.86
※ 編輯: tkcn 來自: 140.122.183.199 (06/28 09:17)
推
06/28 11:46, , 1F
06/28 11:46, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12