L - The Smallest String Concatenation
CodeForces - 632C
You're given a list of n strings a1,?a2,?...,?an. You'd like to concatenate them together in some order such that the resulting string would be lexicographically smallest.
Given the list of strings, output the lexicographically smallest concatenation.
Input
The first line contains integer n — the number of strings (1?≤?n?≤?5·104).
Each of the next n lines contains one string ai (1?≤?|ai|?≤?50) consisting of only lowercase English letters. The sum of string lengths will not exceed 5·104.
Output
Print the only string a — the lexicographically smallest string concatenation.
Example
Input
4
abba
abacaba
bcd
er
Output
abacabaabbabcder
Input
5
x
xx
xxa
xxaa
xxaaa
Output
xxaaaxxaaxxaxxx
Input
3
c
cb
cba
Output
cbacbc
題意:對給定字符串排序壁袄,使排序后的字典序最小
解法:自定義sort函數(shù)的比較函數(shù)cmp,對字符串進(jìn)行排序,然后依次輸出碌补。比較函數(shù)即比較兩個字符串誰放在前面字典序小黍特,所以比較a+b和b+a
代碼:
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
string n[50005];
bool cmp(string a,string b)
{
return a+b<b+a;
}
int main()
{
int num;
cin>>num;
for(int i=0;i<num;i++)
cin>>n[i];
sort(n,n+num,cmp);
for(int i=0;i<num;i++)
cout<<n[i];
return 0;
}