推 pandix: 確實 我覺得你那篇證的比較好 10/29 16:24
※ 引述《pandix (麵包屌)》之銘言：
: 2136. Earliest Possible Day of Full Bloom
: 如果先種 1:
: p1 g1
: ------- -----
: p2 g2
: ------- ------
雖然有點像在挑毛病，不過要用 swap 的方式來證其實有點小麻煩
因為上面這個證法只適用在相鄰的情況
如果像是
p1 g1
------ -------
p2 g2
------- -------
p3 g3
----------------- ------
如果問的是 1 跟 3 是否能夠互換，就變得沒有很明顯了
因為換了之後會把 2 往後頂
所以要證明 sort 的情況是最佳解
就變成還要證明可以光靠 swap 兩兩相鄰的種子就能 sort
幸好 bubble sort 就符合這個條件
所以就變成要證明 bubble sort 的演算法是對的
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667031363.A.B59.html