https://www.luogu.com.cn/problem/P1012
将每个数用字符串的形式读进来,对于任意两个数 x x x, y y y,如果 x + y > y + x x+y>y+x x+y>y+x,对最后的答案来说, x x x一定排在 y y y的前面。
简单证明:假设最后的答案为 a 1 a 2 … … a n a_1a_2……a_n a1a2……an,任意相邻的两个一定满足 a i + a i + 1 > a i + 1 + a i a_i+a_{i+1}>a_{i+1}+a_i ai+ai+1>ai+1+ai,否则更改顺序一定会更优,因此下面只需要证明,对于 x + y > y + x x+y>y+x x+y>y+x且 y + z > z + y y+z>z+y y+z>z+y一定有 x + z > y + z x+z>y+z x+z>y+z就可以证明我们cmp排序后得到的答案就是最优解,即证明传递性,
cmp排序的底层原理:
#include<bits/stdc++.h>
#define endl '\n'
#define pii pair<int,int>using namespace std;const int maxn = 23;
string s[maxn];bool cmp(string x,string y)
{// 例如 x=9 y=8 保证9一定在8的前面return x+y>y+x;
}void solve()
{int n; cin>>n;for(int i=1;i<=n;i++)cin>>s[i];sort(s+1,s+1+n,cmp);for(int i=1;i<=n;i++)cout<<s[i];
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T; T=1;while(T--) solve();return 0;
}