题解 CF1321C 【Remove Adjacent】

· · 题解

1 题意简述

输入一个小写字母字符串 S(|S|\leq 100) ， 对于所有的字符，如果左右有这个字符的前继则可以删除，删除后会形成新的序列，问最多能删除多少的字符。

2 思路简述

贪心，最后的字符留着没有意义，能删则删

模拟链表

从后往前枚举即可

3 代码

#include<bits/stdc++.h>
using namespace std;
int a[1003],nxt[1003],pre[1003];
int main()
{
    int n,ans=0;
    scanf("%d",&n);
    char ch=getchar();
    for(int i=1; i<=n; i++) ch=getchar(),a[i]=(int)ch-(int)'a'+1,nxt[i]=i+1,pre[i]=i-1;
    int head=0,tail=n+1;
    nxt[0]=1,pre[n+1]=n;
    for(int i=26; i>1; i--) 
    {
        int now=nxt[head];
        while(now!=tail) 
        {
            if((a[pre[now]]==i-1 || a[nxt[now]]==i-1) && a[now]==i) 
            {
                pre[nxt[now]]=pre[now],nxt[pre[now]]=nxt[now],ans++;
                if(now==head) nxt[now]=head;
                if(now==tail) pre[now]=tail;
                if(now==head) now=nxt[now]; else now=pre[now];
            }
            else
            now=nxt[now]; 
        }
    }
    cout<<ans;
    return 0;
}

4 评价

赛时想出做法所用时间:9min

比赛A掉所用时间:35min

建议难度:橙/黄

链表好难调/kk