alan23273850 的刷題筆記
b051: 2. 排列最大值
Tags: greedy, self-thinking-proof
出處：https://zerojudge.tw/ShowProblem?problemid=b051
提交：https://zerojudge.tw/Submissions?problemid=b051&account=allllllan123456
問題：給定 $n\in[1,100]$ 個 int 範圍的正整數 arr[1:n]，請問如何將這些數字重新排列才能使得連接之後整體的值最大？
解法：這題作法不難，但證明需要想一下，先說解法，其實就是排序，對於兩數 x、y 如果有 x.y $\ge$ y.x，其中 . 表連接，就會把 x 擺前面 (高位數)，舉例來說，讓 x=33、y=320，因為 33320 $\ge$ 32033，所以會讓 x 擺前面。每個正整數序列的排序結果都是唯一的。
證明：定義兩正整數 x、y 有 x $\Rightarrow$ y 的關係如果 x.y $\ge$ y.x，有 x $\Leftrightarrow$ y 的關係如果 x.y = y.x，那麼 [1] x $\Rightarrow$ y 和 y $\Rightarrow$ z 可以推得 x $\Rightarrow$ z；(2) x $\Rightarrow$ y 和 y $\Rightarrow$ x 可以推得 x $\Leftrightarrow$ y。根據 [1]，這些正整數必定能排成一個有序列 A: arr[1] $\Rightarrow$ arr[2] $\Rightarrow$ … $\Rightarrow$ arr[n-1] $\Rightarrow$ arr[n]，現在我想說明這個排序就是我們想要的，有趣的是，雖然最佳解只有一個，但滿足這個順序的排列卻未必只有一種，先定義此時的「國王」(最左邊的正整數) 為 arr[1]。先從反面來看，如果存在一個最左邊 (假設是 arr[i]) 不是國王的有序列亦為最佳解，它必定形如 B: arr[i] $\Rightarrow$ … $\Rightarrow$ arr[1] $\Rightarrow$ … $\Rightarrow$ arr[n]，但是根據 [1] 我們又知道 A 會有 arr[1] $\Rightarrow$ arr[i]、B 會有 arr[i] $\Rightarrow$ arr[1]，再根據 (2) 就會得到 arr[i] $\Leftrightarrow$ … $\Leftrightarrow$ arr[1] 的結論，這意味著我可以從 B 的 arr[1] 的位置開始往左持續交換到國王的位置而且過程中保持整體的值不變，而這個動作也意味著最佳解必定會被包含在以 arr[1] 為國王的序列 A 裡面，所以直接以 arr[1] 作為第一個元素必定能走向最佳解。選定 arr[1] 之後，定義最佳排列為 P$_1$ = arr[1].P$_2$，那針對剩下的元素我們也要設法想出子問題 P$_2$ 的最大排列，但根據上述的說明我們又能斷定「以 arr[2] 為 P$_2$ 的國王」必定能讓 P$_2$ 走向最佳排列，所以讓 arr[2] 接在 arr[1] 的後面，整個問題就會繼續演變成 P$_1$ = arr[1].arr[2].P$_3$ = arr[1].arr[2].arr[3].P$_4$ = arr[1].arr[2].arr[3].arr[4].P$_5$ = … = arr[1].arr[2]…..arr[n-1].arr[n]，而這就是我們要的最佳排列。
附註：
[1] 這題讓我思考最久的地方就是為什麼 x.y $\ge$ y.x 和 y.z $\ge$ z.y 可以推得 x.z $\ge$ z.x，它的證明非常技巧性，可以先觀察到第一個式子其實可以寫成 $x\cdot10^{|y|} + y\ge y\cdot10^{|x|} + x$，其中 |.| 表示一個正整數的位數，它可以再繼續改寫成 $x\cdot(10^{|y|}-1)\ge y\cdot(10^{|x|}-1)\gt0$，同理第二個不等式亦可以改寫成 $y\cdot(10^{|z|}-1)\ge z\cdot(10^{|y|}-1)\gt0$，把上面兩式相乘會得到 $$x\ (10^{|z|}-1)\cdot y\ (10^{|y|}-1)\ge z\ (10^{|x|}-1)\cdot y\ (10^{|y|}-1)\gt0$$ 同除以 $y\ (10^{|y|}-1)$ 會得到 $x\cdot (10^{|z|}-1)\ge z\cdot (10^{|x|}-1)$，展開移項得到 $x\cdot10^{|z|} + z\ge z\cdot10^{|x|} + x$ 也就是 x.z $\ge$ z.x 了！
延伸：此證明可否推廣到非負整數的情況呢？也就是多考慮一個整數 0。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int n, arr[100];
6 while (cin >> n) {
7 for (int i=0; i<n; i++) cin >> arr[i];
8 sort(arr, arr+n, [](int a, int b){
9 string s1 = to_string(a);
10 string s2 = to_string(b);
11 return stoi(s1 + s2) >= stoi(s2 + s1);
12 });
13 for (int i=0; i<n; i++) cout << arr[i];
14 cout << '\n';
15 }
16 return 0;
17}