4.5 起名2

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

为了排解巨大的学习压力，小明养成了一个奇特的爱好：在宿舍养蚂蚁。

小明想给最大的那只蚂蚁起一个霸气的名字，为此他想了很多候选名字，但他选来选去也无法决定要用哪个名字。突然他想到，如果把所有的候选名字按某种顺序首尾相接串起来，就可以得到一个非常霸气的名字了。当然为了让最终的名字更加霸气，小明希望这个最终的结果的字典序尽可能大。现给出\(n\)个候选名字，你要帮小明安排一个最优的顺序将它们首尾相接串起来，使得最终得到的那个名字字典序尽可能大(字典序的定义请参考4.4 起名1）。

数据输入

输入一行为\(n\)，表示字符串的个数。以下\(n\)行，每行给出一个字符串。\(1\leq n\leq 10000\)。字符串仅由小写字母组成，\(1\leq\)字符串长度\(\leq 50\)。

数据输出

输出一个字符串，为所有输入字符串按照某种顺序串起来后，有可能得到的字典序最大的结果。

输入示例 输出示例
2
c
cav		 ccav

数据范围

\(70\%\)的测试点，\(n\leq 10\)；\(30\%\)的测试点，\(n\leq 10000\)。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define maxn 10005
#define maxm 51
char str[maxn][maxm], temp1[maxm << 1], temp2[maxm << 1];
int index[maxn];

bool cmp(int a, int b){
    strcpy(temp1, str[a]);
    strcpy(temp2, str[b]);
    return strcmp(strcat(temp1, str[b]), strcat(temp2, str[a])) > 0;
}

int main(){
    int n, i;
    scanf("%d\n", &n);
    for (i = 0; i < n; ++i){
        gets(str[i]);
        index[i] = i;
    }
    sort(index, index + n, cmp);
    for (i = 0; i < n; ++i){
        printf("%s", str[index[i]]);
    }
    puts("");
    return 0;
}

设计思路与复杂度分析

n个字符串串成一个长串，使得长串字典序最大。大小具有传递性，拼接两个串比较大小即可确定两个串的相对顺序。复杂度\(O(nlogn\times maxlen)\)。

0%