【题目描述】
小明有一个字符串，由小写英文字母组成。
小明准备对他的字符串进行改造，改造的方法是删除字符串中间的一部分字符。小明希望改造完后，新的字符串中的相邻字符都满足左边的字符小于等于右边的字符（a < b < ... < z）。
例如，对于字符串 happy，小明可以删除第一个字母，变成 appy，满足要求。或者小明删除第二字母，变成 hppy，也满足要求。小明还有其他方法使得结果满足要求。再如，对于字符串 autumn，可以删除 3 个字母变成 amn，或者删除 4 个字母变成 at。其他满足要求的方案还有很多。
小明想知道，对于一个字符串，至少要删除多少个字母能满足要求。
【输入】
输入一行包含一个字符串。
【输出】
输出一行，包含一个整数，表示最少要删除的字母个数。
【输入样例】
happy
【输出样例】
1
【代码详解】
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;const int N = 100005;
string s; // 输入字符串
int n, a[N], b[N], f[N], maxn, len; // n: 字符串长度，a: 字符转换为数字，b: 递增子序列数组，f: 以i结尾的最长不下降子序列长度int main()
{cin >> s; // 读入字符串n = s.size(); // 获取字符串长度s = " " + s; // 在字符串前加一个空格，使下标从1开始// 将字符转换为数字（a=0, b=1, ..., z=25）for (int i = 1; i <= n; i++){a[i] = s[i] - 'a';}// 调试输出// for (int i=1; i<=n; i++)// cout << a[i] << " ";// cout << endl;// 计算最长不下降子序列的长度for (int i = 1; i <= n; i++){if (a[i] >= b[len]) // 如果当前字符大于等于b数组末尾元素{b[++len] = a[i]; // 将当前字符添加到b数组末尾f[i] = len; // 记录以i结尾的最长不下降子序列长度}else{// 二分查找第一个大于a[i]的位置int m = upper_bound(b + 1, b + len + 1, a[i]) - b;b[m] = a[i]; // 用a[i]替换找到的位置f[i] = m; // 记录以i结尾的最长不下降子序列长度}}// 调试输出// for (int i=1; i<=len; i++)// cout << b[i] << " ";// cout << endl;// 输出需要删除的字符数// 总字符数减去最长不下降子序列的长度cout << n - len;return 0;
}
【运行结果】
happy
1