题解 | #Inverted World#

这一题字符串可能变为零或者一开头的，要求出两个答案，最后取最小操作次数，设置两个常数c0和c1，表示最终需要操作的以0和1结尾的字符串个数，在输入时找到需要反置的字符，通过常数c0和c1接到之前的需要进行操作的字符串后面或者新开字符串，最后统计c0和c1的个数，找到答案（如果直接用队列进行暴力求解的话会超时）

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        int ans1=0,ans2=0;
        string s;cin>>s;
        int c0=0,c1=0;
        for(int i=1;i<=n;i++){
            if(s[i-1]=='0'&&(i+1)%2==1){
                if(c1!=0) c1--;
                c0++;
            }
            else if(s[i-1]=='1'&&(i+1)%2==0){
                if(c0!=0) c0--;
                c1++;
            }
        }
        ans1=c0+c1;
        c1=0,c0=0;
        for(int i=1;i<=n;i++){
            if(s[i-1]=='0'&&i%2==1){
                if(c1!=0) c1--;
                c0++;
            }
            else if(s[i-1]=='1'&&i%2==0){
                if(c0!=0) c0--;
                c1++;
            }
        }
        ans2=c0+c1;
        cout<<min(ans1,ans2)<<"\n";
    }
}