【蓝桥杯】删除字符

【蓝桥杯】删除字符 删除字符

给定一个单词，请问在单词中删除 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#include #include 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%sn", pre_str[0], str + t + 1); return 0; } 暴力解法(貌似这个是正确的)

因为上面的思路是我自己想的，刚开始也不知道是不是正确的(因为题目数据太水)，但之后遇到一道类似的题发现A不掉(仅差两个点……)，所以还是回归暴力吧，毕竟这题的字符串长度也就100。

思路

这里思路发生了变化，使用贪心法，删掉靠前的并且大于它后面一个字符的字符，如果整个字符串是递增的话，那么就删除最后一个字符每删除一个字符后都会得到一个新的字符串，又要从头开始遍历，循环往复(可知时间复杂度有多高)，直到删完 t t t 个字符这里的“删除字符”是字面意思，即暴力地移动后面的字符来覆盖需要删除的字符 代码如下

#include 
#include 
using namespace std;

char str[105];  //字符串
int t;          //要删去的字符数目

int main(void) {
    scanf("%s%d", str, &t);
    int len = strlen(str);
    int i = 0, j = 0;  //临时变量
    //删够t个字符后退出循环
    while (t) {
        for (i = 0; i < len - 1; i++) {
            //“删去字符”，直接用右边的字符覆盖掉即可
            if (str[i] > str[i + 1]) {
                for (j = i; j < len - 1; j++) {
                    str[j] = str[j + 1];
                }
                break;
            }
        }
        len--;  //删去一个字符，字符串长度减1
        str[len] = '';//处理字符串递增的情况
        t--;
    }
    puts(str);
    return 0;
}

其实第一个思路是有问题的(其实说实话我都不知道我是怎么想出来的)，但我还是把它保留下来，希望以后有所改进吧。