删除字符

给定一个单词，请问在单词中删除 t 个字母后，能得到的字典序最小的单词是什么？

输入描述
输入的第一行包含一个单词，由大写英文字母组成。

第二行包含一个正整数 t。

其中，单词长度不超过 100，t小于单词长度。

输出描述
输出一个单词，表示答案。

输入输出样例
示例 1
输入

LANQIAO
3

输出

AIAO

初看还挺简单，但实际上我认为需要考虑的细节还挺多的(以我的思路来看的话)，为了方便，设字符串长度为len

• 思路：在前t+1个字符中找出最小的字符，再把这个字符和之后的字符串(后len-t-1个字符组成的字符串)拼接起来即可

虽然有不少的人都是这么想的，题目用这种方法也能过，不过不太严谨
比如这个例子

LANQIAO
5

同样是示例，删去5个字符得到的最小字符串是什么呢？
如果用以上思路，得到的答案会是AO，但是仔细一想，AO真的是最小的吗？
这里面不是有两个A吗，那当然是AA最小了，那为什么输出的不是AA?
其实答案就是AA，只不过这道题数据太水，根本没卡这个点，所以上述的思路也能过。

我认为的 “正解”

上面的思路给了我一点启发，虽然我也不知道自己的思路是否是正确的，但是还是把它记录下来

• 将整个字符串分为[0,t]和[t+1,len)两部分
• 在第一部分中，找出一个"最小字符串"pre_str，然后和第二部分字符串合并

找最小字符串

• 首先找出[0,t]部分中最小的字符min_ch，并计数，设为cnt，并且把最后一个最小字符的下标记录下来，设为last_pos
• 把找到的cnt个最小字符min_ch装到pre_str中
• 将区间起点变为last_pos+1，重复上述过程，直到起点>t为止
• 由此可得到“最小字符串”pre_str
• 设一个“指针”i用于遍历pre_str，j用于遍历第二部分字符串，即str[t+1,len)
• 判断i和j所指的字符，如果pre_str[i]<=str[j]，则str[j]替换为pre_str[i]，否则i++
• 终止条件为i<pre_str.length&&j<str.length
• 最后把pre_str[0]和str+t+1拼接起来即可

代码如下

#include <cstring>
#include <iostream>
using namespace std;

char str[105];//用于存储输入字符串
char pre_str[105];//最小字符串
int cc[26];//用于统计字符个数
int t;//要删去的字符个数
int last_pos;//最后一个最小字符的下标
int pos;//起始位置

//用于生成最小字符串
void deal_str(int start) {
    if (start > t) return;
    memset(cc, 0, sizeof(cc));
    char min_ch = 'Z' + 1;
    for (int i = start; i <= t; i++) {
        cc[str[i] - 'A']++;
        if (str[i] <= min_ch) {
            min_ch = str[i];
            last_pos = i;
        }
    }
    for (int i = pos; i < pos + cc[min_ch - 'A']; i++) {
        pre_str[i] = min_ch;
    }
    pos += cc[min_ch - 'A'];
    deal_str(last_pos + 1);
}

int main(void) {
    scanf("%s%d", str, &t);
    deal_str(0);
    //这个好像叫双指针吧
    int l = 1, r = t + 1;
    while (l < pos && str[r]) {
        if (str[r] >= pre_str[l]) {
            str[r] = pre_str[l];
            l++;
            r++;
        } else {
            l++;
        }
    }
    //输出拼接之后的字符串
    printf("%c%s\n", pre_str[0], str + t + 1);
    return 0;
}