A27723. 字符串改造(trans.cpp)问题描述小明有一个字符串，由小写英文字母组成。小明准备对他的字符串进行改造，改造的方法是删除字符串中间的一部分字符。小明希望改造完后，新的字符串中的相邻字符都满足左边的字符小于等于右边的字符（a < b < … < z）。 例如，对于字符串 happy，小明可以删除第一个字母，变成 appy，满足要求。或者小明删除第二字母，变成 hppy，也满足要求。小明还有其他…
填空题
中等
知识点
题目描述
字符串改造(trans.cpp)
问题描述
小明有一个字符串，由小写英文字母组成。
小明准备对他的字符串进行改造，改造的方法是删除字符串中间的一部分字符。
小明希望改造完后，新的字符串中的相邻字符都满足左边的字符小于等于右边的字符（a < b < … < z）。
例如，对于字符串 happy，小明可以删除第一个字母，变成 appy，满足要求。或者小明删除第二字母，变成 hppy，也满足要求。小明还有其他方法使得结果满足要求。
再如，对于字符串 autumn，可以删除 3 个字母变成 tmn，或者删除 4 个字母变成 at。
其他满足要求的方案还有很多。
小明想知道，对于一个字符串，至少要删除多少个字母能满足要求。
输入格式
从文件 trans.in 中输入数据。
输入一行包含一个字符串。
输出格式
输出到文件 trans.out 中。
输出一行，包含一个整数，表示最少要删除的字母个数。
样例输入
happy
样例输出
1
样例输入
autumn
样例输出
3
评测用例规模与约定
注意：以下规模是评测时输入数据一定会满足的限制，在你的程序中不需要对这些限制进行检查。
对于 30%的评测用例，字符串的长度不超过 20；
对于 60%的评测用例，字符串的长度不超过 1000；
对于 80%的评测用例，字符串的长度不超过 10000；
对于所有评测用例，字符串的长度不超过 100000。
参考答案
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int len[30] = {};
int main()
{
freopen("trans.in", "r", stdin);
freopen("trans.out", "w", stdout);
string s;
cin >> s;
int siz = s.size();
for (int i = 0; i < siz; i++)
{
for (int j = s[i] - 'a'; j >= 0; j--)
{
len[s[i] - 'a'] = max(len[s[i] - 'a'], len[j] + 1);
}
}
int mx = 0;
for (int i = 0; i < 26; i++)
{
mx = max(mx, len[i]);
}
cout << siz - mx << endl;
return 0;
}
上一题
下一题