最小字符串 蓝桥杯 C++

时间限制1s

内存限制128MB

难度3

题目描述

给定一些字符串(只包含小写字母)，要求将他们串起来构成一个字典序最小的字符串。

输入

　　第一行T,表示有T组数据。 　　接下来T组数据 　　每组第一行一个正整数n，表示字符串个数。 　　接下来n行，每行一个字符串(长度不超过100)。

输出

T行，每行一个字符串。

输入样例1

1 3 a b c

输出样例1

abc

输入样例2

11 4 ba b baba babb 4 b ba ba bb 4 b bb b ba 3 a ab ac 8 a ab abc b bc ba cba ac 3 a a acd 3 a b aac 3 a bc bd 3 a c aab 3 a c ab 3 b ba d

输出样例2

bababababbb bababbb babbbb aabac aababcacbabbccba aaacd aaacb abcbd aaabc aabc babd

思路分析

将一些字符串串起来构成一个字典序最小的字符串，其实就是怎么排序这些字符串的问题。

如果直接根据单个字符串的大小来排序的话，我们首先来看看，字符串大小是怎么比较的？

首先会从第一个字符开始比较，根据字符的ASCII码的大小来比较，直到遇到字符的结束符为止，那么长的字符串就有可能比短的字符串要小的。

举个例子吧，像z和za这两个字符串，如果是安装单个字符串来排，那么最小是zza，而显然最小应该是zaz。

所以我们要根据组合最小来排序。

AC代码

#include<iostream>
#include<algorithm>
using namespace std;
bool rule(string a, string b)
{
	return (a + b) < (b + a);
}
int main() 
{
	int n, i, t;
	cin >> t;
	while (t--) 
	{
		cin >> n;
		string *p = new string[n];
		for (i = 0; i < n; i++)
			cin >> p[i];
		sort(p, p + n, rule);
		for (i = 0; i < n; i++)
			cout << p[i];
		cout << endl;
		delete[] p;
	}
}