1038 Recover the Smallest Number

题目描述
解题思路：具体看y总描述，（偏序关系证明）还是有点略懵。
具体贪心证明：每个字符串要满足<关系，这个<关系是自己人为定义的。
具体关系如下：若a<=b 等价于 ab<=ba。 其中ab表示拼接。
有了这个关系之后，使用sort排序，从低到高进行拼接就可以了。
证明为什么这么拼接可以是最优的
假设现在最优解序列为$a_1{a}_2{a}_3{a}_i{a}_{i+1}{a}_n$。使用反证法，如果不满足每个字符串都是我们定义的<关系，则必然存在一个$a_i>a_{i+1}$，则等效于$a_i{a}_{i+1}>a_{i+1}{a}_i$,那我们完全可以将$a_i与a_{i+1}$进行位置互换变为$a_1{a}_2{a}_3{a}_{i+1}{a}_i{a}_n$，其余不变，中间这段变小了，则原序列就不是最优解，假设矛盾。

至于为什么不能直接对字符串字典序排序，而需要定义新的比较方式。那是因为我们用下面的做法，但是无法使用反证法证明出这样贪心是最优的。因为在反证法过程中：$a_i>a_{i+1}$你无法保证交换完顺序之后，拼接的时候$a_i{a}_{i+1}$>$a_{i+1}{a}_i$，如：8677 867 8677867 < 8678677

#include
#include
#include
using namespace std;
const int N = 1e5+10;
string s[N];
int cmp(string a,string b){
    return a+b < b+a;
}
int main(){       
    int n;
    cin>>n;
    for(int i = 0;i < n;i++) cin>>s[i];
    sort(s,s+n,cmp);
    string res = "";
    for(int i = 0;i < n;i++) res += s[i];
    int i = 0;
    while(i + 1 <= res.length()-1 && res[i] == '0') i++;
    cout<<res.substr(i);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21