4.4 起名1

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

实验任务

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

小明想给最大的那只蚂蚁起一个霸气的名字，为此他发明了“程序员起名法” 。具体步骤如下：1.~随机生成一个字符串；2. 选择字符串中字典序最大的子序列作为名字。作为一个优秀的程序员，小明顺利地完成了第一步，但第二步他就不会了，请你帮帮他。

子序列的定义：对于一个字符串\(s=s_1s_2\cdots s_{|s|}\)，称字符串\(s_{p_1}s_{p_2}\cdots s_{p_k}\ (1\leq p_1<p_2<\cdots < p_k\leq |s|)\)为它的一个子序列。

字典序的定义：字符串\(x=x_1x_2\cdots x_{|x|}\)比字符串\(y=y_1y_2\cdots y_{|y|}\)字典序大，当且仅当： 1.~\(|x|>|y|\)且\(x_1=y_1,x_2=y_2,\cdots ,x_{|y|}=y_{|y|}\)， 或 2.~存在一个非负整数\(r\ (r<|x|,r<|y|)\)，使得\(x_1=y_1,x_2=y_2,\cdots ,x_r=y_r\)且\(x_{r+1}>y_{r+1}\)。字符的大小即它们 ASCII 码的大小。

数据输入

输入一行为一个字符串，表示小明第一步的结果。

字符串仅由小写字母组成，\(1\leq\)字符串长度\(\leq 100000\)。

数据输出

输出一个字符串，为输入字符串的字典序最大的子序列。

输入示例 输出示例
ababba bbba

数据范围

\(70\%\)的得分点，输入字符串长度\(\leq 10\)；\(30\%\)的得分点，输入字符串长度\(\leq 100000\)。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <string.h>
#define maxn 100005
char str[maxn];
int pos[maxn];

int main(){
    int i, n;
    gets(str);
    n = strlen(str);
    pos[n - 1] = n - 1;
    pos[n] = n;
    for (i = n - 2; i >= 0; --i){
        if (str[i] >= str[pos[i + 1]])pos[i] = i;
        else pos[i] = pos[i + 1];
    }
    for (i = pos[0]; i < n; i = pos[i + 1])
        putchar(str[i]);
    puts("");
    return 0;
}

设计思路与复杂度分析

考虑输出的第一个字符，必然是字符串中出现的最大字符。如果有多个最大字符，那么第二个、第三个字符也应该是最大字符，才能保证字典序最大。

当最大字符用完之后，则考虑次大字符。这个次大字符不能出现任意一个最大字符之前，否则会导致字典序变小。也就是说之后输出的所有字符必须在所有最大字符后面，原串成为一个后缀串，在该后缀串找字典序最大的子序列，就是规模更小的子问题。

0%