习题8-7 字符串排序 (20 分)

### 回答1：
题目描述

给定N个字符串（从1开始编号），请你将所有字符串按照字典序从小到大排序，输出排序后的结果。

输入格式：

输入第一行给出一个正整数N（≤10^4），表示字符串总数。随后N行，每行包含一个长度不超过100的非空字符串，由大小写英文字母、数字和“_”（代表空格）组成，以回车结束。

输出格式：

输出文件共N行，为按字典序排序后的字符串，即排序后第i行就是原序列中第i个字符串（从1开始编号）。

输入样例：

3
nowcoder
_what_are_you_waiting_for
welcome_to_nowcoder_com

输出样例：

_what_are_you_waiting_for
nowcoder
welcome_to_nowcoder_com

思路分析

本题可以使用sort函数进行排序，sort函数的第三个参数可以自定义排序规则，即自定义比较函数。

比较函数的定义格式为：

bool cmp(string a, string b){
return a < b;
}

其中，cmp函数返回值为bool类型，表示a是否小于b，如果a小于b，则返回true，否则返回false。

在本题中，需要按照字典序从小到大排序，因此可以直接使用string类型的小于运算符进行比较。

代码实现

### 回答2：
题目描述：

将n个字符串按照字典序从小到大排序。

输入格式：

第一行一个正整数n(1<=n<=100)，表示字符串的个数。

接下来n行为该字符串,字符串长度不超过100，且保证所以字符串均由小写字母组成。

输出格式：

输出排序后的n个字符串，每个字符串一行。

样例输入：

5
a
ab
cba
aa
ac

样例输出：

a
aa
ab
ac
cba

题目分析：

我们可以用c++中的sort函数来完成这个问题，但是需要将其拆分成两个步骤。

第一步：新建一个排序函数sortString，这个函数的输入是两个字符串，返回值为bool类型。这个函数主要完成比较操作，如果字符串a小于字符串b，返回真；否则返回假。

第二步：在主函数中，首先输入n和n个字符串，将这n个字符串存放在一个字符串数组str[]中。然后，调用sort函数来对这个字符串数组进行排序，排序依据是sortString这个函数。

程序代码：

### 回答3：
题目描述：
输入多个字符串，按字典序排序输出。如果两个字符串彼此包含，那么就输出最长的那个字符串。如果两个字符串长度一致，那么就按字典序进行排序。

解题思路：
首先，需要至少两个字符串才能进行比较，所以需要判断输入的字符串个数是否大于等于2。
其次，需要为每个字符串建立一个字符串数组来存放每个字符串，然后按照字典序进行快排。
接着，对于两个字符串中存在相互包含的情况，需要先进行比较它们的长度，取较长的那个字符串输出。
最后，对于多个字符串的情况，我们可以先将所有字符串按照字典序进行排序，然后再依次判断相邻的字符串是否存在包含关系。如果包含，就输出较长的那个字符串。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200010;
const int INF=0x3f3f3f3f;
int n,m,sum;
int sz[MAXN],maxs[MAXN],f[MAXN],ans;
int vis[MAXN],hash[MAXN];
char s[MAXN];
struct node{
int u,v,w;
}edge[MAXN];
bool cmp(int a,int b){return sz[a]<sz[b];}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void Union(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy) return;
f[fx]=fy;
sz[fy]+=sz[fx];
maxs[fy]=max(maxs[fx],maxs[fy]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
}
sort(edge+1,edge+1+n,[](const node&x,const node&y){return x.w>y.w;});
for(int i=1;i<=n;i++){
int u=edge[i].u,v=edge[i].v,w=edge[i].w;
if(find(u)==find(v)) continue;
int fu=find(u),fv=find(v);
sum+=w*(sz[fu]*maxs[fv]+sz[fv]*maxs[fu]);
ans+=(sz[fu]+sz[fv])*w;
maxs[fu]=max(maxs[fv],w),Union(u,v);
}
printf("%d",sum*2/ans);
return 0;
}

其中，使用了带权并查集来维护每个连通块的大小和最长边权。按照边权从大到小排序，然后进行合并，在合并过程中顺便维护连通块的最大边权。最后再遍历一次所有的边，计算出最小生成树的权值和2倍除以原图的权值和，即为结果。