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%