试题 算法提高 最小字符串
时间限制:2.0s 内存限制:256.0MB
问题描述
给定一些字符串(只包含小写字母),要求将他们串起来构成一个字典序最小的字符串。
输入格式
第一行T,表示有T组数据。
接下来T组数据
每组第一行一个正整数n,表示字符串个数。
接下来n行,每行一个字符串(长度不超过100)。
输出格式
T行,每行一个字符串。
样例输入
1
3
a
b
c
样例输出
abc
数据规模和约定
T<=7000,n<=100;
基本思路
构造一个二维字符串数组a[7000][100]一次读入T组数据,并用n[700]记录每组字符串个数n,然后调用algorithm库中的sort排序函数,并自定义排序规则cmp为最小字典序,最后遍历数组 A[7000][100]输出结果。
程序代码
#include<iostream>
#include<algorithm>
using namespace std;
string a[7000][100];
bool cmp(string s1, string s2)
{
string s3 = s1 + s2;
string s4 = s2 + s1;
if (s3.compare(s4) < 0) return true;
else return false;
}
int main()
{
int size,j=0;
int n[7000];
cin >> size;
for (int j = 0; j < size; j++)
{
cin >> n[j];
for (int i = 0; i < n[j]; i++)
{
cin >> a[j][i];
}
}
for (int j = 0; j < size; j++)
{
sort(a[j], a[j] + n[j], cmp);
for (int i = 0; i < n[j]; i++)
cout << a[j][i];
cout << endl;
}
return 0;
}
注意事项
(1)应将字符串数组a[7000][100]定义为全局变量,这样可以把数组数据存储在数据段(全局区)。因为这个数组比较大,如果定义在主函数里,编译系统会在堆栈区开辟存储空间,但由于默认堆栈帧大小为 16 KB,对于内核模式为 1 KB,所以会出现堆栈溢出异常。
(2)string 类的比较 用compare() 函数非常方便,而且能区分字母的大小写,若参与比较的两个串值相同,则函数返回 0;若字符串 S 按字典顺序要先于 S2,则返回负值;反之,则返回正值。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)