※ 引述《friendever (michael)》之銘言：
: → Schottky:我找到方法了,出乎意料地簡單 =.=
: → azureblaze:可惜推文長度寫不下
: → Schottky:先取一個積分最高的,再尋找下一個候選人讓兩數總積分最高
: → Schottky:如此一個一個找,複雜度只有O(n^2)
: → cismjmgoshr:(3,3)(1,6)(6,1)選2組,樓上作法碰到這組會有什麼結果?
: → Schottky:k=2時會出槌沒錯,但是n和k都很大的時候,Σx>>x,Σy>>y
: → Schottky:此時就不會出現你說的情形了
我在考慮一個 worst case: 令 n = 2m+1, m 是正整數, 資料是:
(500,500) (1000,0) (0,1000) (1000,0) (0,1000) (1000,0) (0,1000) .....
沒有說不能重複, 所以就讓 (1000,0) (0,1000) 這一對活寶重複到底
當 k 是奇數時, 最佳組合是 (500,500) 和各 (k-1)/2 個 (1000,0) 及 (0,1000)
這個狀況用我提的方法沒有問題。
當 k 是偶數時, 最佳組合是各 k/2 個 (1000,0) 及 (0,1000),
從頭到尾都不該選 (500,500)
但用我的方法, 不管前面怎麼改良, 假如前 2x 步都沒有選到 (500,500),
在第 2x+1 步時選 (500,500) 的積分永遠還是比選 (1000,0) 多 2500 分...
(1000x+500)*(1000x+500) - (1000x+1000)*(1000x+0)
= (1000000x^2+1000x+2500) - (1000000x^2+1000x+0) = 2500
所以我說當 k 夠大時就沒問題... 其實在這個 special case 還是有點小問題...
不過我覺得這個思考方向還是很有前途的。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.8.240