简答题
偏难
#20727
字符排序 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有 n 个仅包含小写字母的字符串 s 1 ,s 2 ,...,s n ,小杨想将这些字…
字符排序
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有 n 个仅包含小写字母的字符串 s1,s2,...,sn,小杨想将这些字符串按一定顺序排列后拼接到一起构成字符串 t 。小杨希望最后构成的字符串 满足:
假设 ti为字符串 t 的第 i 个字符,对于所有的 j<i 均有 tj≤ti。两个字符的大小关系与其在字母表中的顺序一致,例如e<g<p<s。
小杨想知道是否存在满足条件的字符串排列顺序。
输入格式
第一行包含一个正整数 T TT,代表测试数据组数。
对于每组测试数据,第一行包含一个正整数 n ,含义如题面所示。
之后 n 行,每行包含一个字符串 si。
输出格式
对于每组测试数据,如果存在满足条件的排列顺序,输出 1,否则输出 0。
输入样例
输出样例
样例解释
对于第一组测试数据,一种可行的排列顺序为 aa+ac+de,构成的字符串 t 为 aaacde,满足条件。
对于全部数据,保证有 1≤t,n≤100,每个字符串的长度不超过 10。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include<bits/stdc++.h>
using namespace std;
string s[110];
void bubble_sort(string *a, int n) {
bool flag = true;
while (flag) {
flag = false;
for (int i = 1; i < n; ++i) {
if (a[i] > a[i + 1]) {
flag = true;
string t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
}
}
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
}
bubble_sort(s, n);
string t="";
for(int i=1;i<=n;i++){
t+=s[i];
}
int m = t.size();
int fl=1;
for(int i=1;i<m;i++){
if(t[i]<t[i-1]){
fl=0;
break;
}
}
cout<<fl<<"\n";
}
}</pre>
这道题暂未补解析。