眾所周知，這題的答案是對輸入的正整數排序，但排序的規則很特別，

定義兩正整數 x --> y if x.y >= y.x，而且 x <--> y if x.y == y.x，其中 . 代表兩整數相接的意思，

我們希望求得的正整數串 a.b.....c.d 裡面起碼任兩個相鄰的正整數 x.y 都要滿足 x --> y 的關係，

因為如果該正整數串的某 x.y 出現 not (x --> y) 的話我勢必就可以把它換過來讓整個正整數串變得更大，

那現在要擔心的問題是滿足第三行條件的正整數串會不會有很多個，如果很多的話那怎麼知道哪個最大呢？

先考慮一個事實就是如果 x --> y 且 y --> z，那麼 x --> z 必定成立 (*)，另外

　　　　　　　　　如果 x --> y 且 y --> x，那麼 x <--> y 也必定成立，

考慮以下的答案構建方法，給定還沒選好的 N 個整數 arr[1:N]，如果 arr[1] --> arr[i] for all i，

那麼就先把 arr[1] 擺在數字最前面，接著剩下的空白再由 arr[2:N] 下去挑，一樣選 arr[2] --> arr[i] for all i >= 2 放在最前面，依序下去，最後得到的 arr[1].arr[2].....arr[N-1].arr[N] 必定是最佳解。

為什麼每次把國王放在最前面就能走向最佳解？考慮一個反例，如果已知 arr[1] --> arr[i] for all i 但是我故意不聽媽媽的話把 arr[2] 放在最前面，而且全部的排序也不違反第三行的規定，而且最後拼成的答案也確實是最佳解，那它應該形如 arr[2].....arr[1].....arr[N]，但是我們又已知 arr[1] --> arr[2]，所以 arr[1] <--> arr[2] 也就是說 arr[2].....arr[1] 這一段的正整數們都有 <--> 的關係，那麼我自然可以透過兩相鄰數交換的方式依次把 arr[1] 換到最前面，而且不改變這整串數字的值 (根據 <--> 的定義)，換言之最佳解一定包含在國王==arr[1] 這個事件裡面，也就是說如果我一開始就聽媽媽的話先把 arr[1] 放在前面，必定可以達到一樣的效果，所以媽媽的話準沒錯。

關於 (*) 的證明，等我在個人網站上面寫好之後，會更新在這裡，有興趣的人也可以試著自己證證看。

(我把字體換小一點)

眾所周知，這題的答案是對輸入的正整數排序，但排序的規則很特別，

定義兩正整數 x --> y if x.y >= y.x，而且 x <--> y if x.y == y.x，其中 . 代表兩整數相接的意思，

我們希望求得的正整數串 a.b.....c.d 裡面起碼任兩個相鄰的正整數 x.y 都要滿足 x --> y 的關係，

因為如果該正整數串的某 x.y 出現 not (x --> y) 的話我勢必就可以把它換過來讓整個正整數串變得更大，

那現在要擔心的問題是滿足第三行條件的正整數串會不會有很多個，如果很多的話那怎麼知道哪個最大呢？

先考慮一個事實就是如果 x --> y 且 y --> z，那麼 x --> z 必定成立 (*)，另外

　　　　　　　　　如果 x --> y 且 y --> x，那麼 x <--> y 也必定成立，

考慮以下的答案構建方法，給定還沒選好的 N 個整數 arr[1:N]，如果 arr[1] --> arr[i] for all i，

那麼就先把 arr[1] 擺在數字最前面，接著剩下的空白再由 arr[2:N] 下去挑，一樣選 arr[2] --> arr[i] for all i >= 2 放在最前面，依序下去，最後得到的 arr[1].arr[2].....arr[N-1].arr[N] 必定是最佳解。

為什麼每次把國王放在最前面就能走向最佳解？考慮一個反例，如果已知 arr[1] --> arr[i] for all i 但是我故意不聽媽媽的話把 arr[2] 放在最前面，而且全部的排序也不違反第三行的規定，而且最後拼成的答案也確實是最佳解，那它應該形如 arr[2].....arr[1].....arr[N]，但是我們又已知 arr[1] --> arr[2]，所以 arr[1] <--> arr[2] 也就是說 arr[2].....arr[1] 這一段的正整數們都有 <--> 的關係，那麼我自然可以透過兩相鄰數交換的方式依次把 arr[1] 換到最前面，而且不改變這整串數字的值 (根據 <--> 的定義)，換言之最佳解一定包含在國王==arr[1] 這個事件裡面，也就是說如果我一開始就聽媽媽的話先把 arr[1] 放在前面，必定可以達到一樣的效果，所以媽媽的話準沒錯。

關於 (*) 的證明，等我在個人網站上面寫好之後，會更新在這裡，有興趣的人也可以試著自己證證看。

https://alan23273850.github.io/Online-Judge-Problems/zerojudge/b0512.-%E6%8E%92%E5%88%97%E6%9C%80%E5%A4%A7%E5%80%BC/

終於把證明補上了 哇哈哈