题目大意

题目链接

给你一个字符串， 如果相邻的两个字母s[i], s[j] 满足 abs(s[i] - s[j]) == 1， 那么就能删除较大的那个字符， 问最多能删多少个。

分析

贪心， 先把字母z删掉， 然后在删y， 以此类推。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

using namespace std;
int ans, n;
string f(string s, char c) {
    int l = s.length();
    string tmp = "";
    // 找到字符c 的连续的区间
    for (int i = 0; i < l; ++i){
        if (s[i] == c){
            int j = i + 1;
            while(j < l && s[j] == c)++j;
            // 判断可不可删
            if (i > 0 && s[i - 1] == c - 1 || j < l && s[j] == c - 1){
                ans += j - i;
                i = j - 1;
                continue;
            }
        }
        // 不能删的被保留
        tmp += s[i];
    }
    // 去除被删的字符, 返回
    return tmp;
}

int main() {
    cin >> n;
    string s;
    cin >> s;
    for (char c = 'z'; c > 'a'; --c)
        s = f(s, c);
    cout << ans << "\n";
    return 0;
}
恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan

千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。