Substring
总提交:176 测试通过:40
描述
Dr lee cuts a string S into N pieces , s[1],……,s[N].
Now , Dr lee gives you these N sub-string:s[1]…,s[N].T there might be several possibilities that the string S could be . For example , if Dr.lee gives you three sub-strings{“a”,”ab”,”ac”},the string S could be “aabac”,”aacab”,”abaac”,…
Your task is to output the lexicographically smallest S.
输入
The first line of the input is a positive integer T.T is the number of the test cases followed.
The first line of each test case is a positive integer N(1<=N<=8) which represents the number of sub-strings.After that,N lines followed. The i-th line is the i-th sub-string s[i].Assume that the length of each sub-string is positive and less than 100.
输出
The output of each test is the lexicographically smallest S.No redundant spaces are needed.
样例输入
1
3
a
ab
ac
样例输出
aabac
题目来源
第九届中山大学程序设计竞赛预选题
代码：
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const string a, const string b)
{
return a +b < b + a;
}
int main()
{
int t;
cin>>t;
while(t--)
{
vector<string>s;
int n;
cin>>n;
string temp;
while(n--)
{
cin>>temp;
s.push_back(temp);
}
sort(s.begin(),s.end(),cmp);
for(int i=0;i<s.size();i++)
cout<<s[i];
cout<<endl;
}
return 0;
}
大家如果对此处的sort（）函数不太明白的话，可以借助下面的例子：
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
bool cmp(const string a, const string b)
{
return a +b < b + a;
}
int main()
{
string a[5];
for (int i = 0 ; i< 5; i++)
cin >> a[i];
sort(a,a+5, cmp);
for (int i = 0 ; i< 5; i++)
cout << a[i] << endl;
}
/* 测试例祝 ：
a, ab , ac, abb , acc;
输出： a, ab, abb , ac, acc;
*/
//这个算法可以应用到 求最小字符串 ， 或最大字符串（通过修改 cmp 来实现）