传送门:D. String Deletion

题意

给你一个长度为$n$,只包含0,1字符的字符串$s$。你可以操作字符串,每次操作是由自己选一个位置$i$并删除$s_i$,之后系统将会自动删除相同字符组成的最长前缀。问最多操作几次才把$s$变成空串。

思路

先将字符串处理成相同字符数组成的数组,比如110010,相同字符数依次是2('11'),2('00'),1('1'),1('0')。然后讨论第一段相同字符数,设其为$prenum$。

  • $prenum>1$。此时删除第1段第1个字符,之后系统删除第1段剩下的字符。
  • $prenum=1$。说明第1段相同字符就只有1个。此时向后找第一个相同字符数大于1的段,删除该段一个字符;若找不到,说明后面相同字符数全部都是1,那么只能把末尾字符删掉。之后系统删除第1段相同字符。

比如处理后的数组是2211,那么:
- option 1:prenum>1,删除第1段第1个字符,数组变为1211,系统自动删除第1段相同字符,数组变为211。
- option 2:prenum>1,删除第1段第1个字符,数组变为111,系统自动删除第1段相同字符,数组变为11。
- option 3:prenum=1,向后找不到大于1的字符段,则删除末尾字符,数组变为1,系统自动删除第1段相同字符,数组变为空。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
char s[N];
vector<int>g;
int main()
{
    ios::sync_with_stdio(false);
    int T,n;
    cin>>T;
    while(T--)
    {
        g.clear();
        cin>>n>>s+1;
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            cnt++;
            if(s[i]!=s[i+1])
            {
                g.push_back(cnt);
                cnt=0;
            }
        }
        int ans=0;
        int p=1;
        for(int i=0;i<g.size();i++)
        {
            if(g[i]>1)
            {
                ans++;
                g[i]=1; 
            }
            else
            {
                bool flag=0;
                while(p<g.size())
                {
                    if(g[p]==1)
                    {
                        p++;
                    }
                    else // 找到了大于1的g[p]
                    {
                        g[p]--;
                        ans++;
                        flag=1;
                        break;
                    }
                }
                if(!flag) // 没找到大于1的g[p],只能从末尾删数
                {
                    ans++;
                    g.pop_back();
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
3
6
110010
12
101010111111
13
1010101111111

ans:
3
6
7
*/

/*
100
1
1
ans:1
2
11
ans:1
2
10
ans:1
3
110
ans:2
3
101
ans:2
4
1010
ans:2
5
10100
ans:3
5
10101
ans:3
5
10110
ans:3
14
11100011100011
ans:5
12
101010111101
ans:6
*/