题目大意

好看串的定义：在长度至少为 $2$ 的子串中， $0$ 的个数要小于等于 $1$ 的个数。

在一串 $01$ 串中你可以在任意位置任意插入 $1$ 或 $0$ 来使得这个串成为好看串，请输出最小的插入数的个数。

解题思路

稍加模拟即可发现，当遇到连续 $2$ 个 $0$ 时，在这 $2$ 个 $0$ 中间插入 $2$ 个 $1$ 即可，当遇到单独的 $1$ 个 $0$ 时，只要在它后面插入 $1$ 个 $1$ 即可。由于我们只需要数出插入的个数，所以不需要对字符串进行改变，遍历一遍，输出答案即可。

时间复杂度 $O(N)$

代码

#include <iostream>
#include <stdio.h>

using namespace std;
string s;
int t,len,ans;
int main(){
    scanf("%d",&t);
    while(t--){
        ans=0;
        scanf("%d",&len);cin>>s;
        for(int i=1;i<len;i++){
            if(s[i]=='0'){
                if(s[i-1]=='0') ans+=2;
                else{
                    if(i-2>=0&&s[i-2]=='0') ans+=1;
                }
            }
        }
        printf("%d\n",ans);
    }
}