题解 | C

题目

输入

输出

思路

使得s中任意两个相邻元素都不相同，存在两种可能10101....或01010....

对于输入的串，只有相同位置不同的需要放入子序列中。

对于子序列如1010111。

只有相邻的数不相同就可以归入一次01反置。

所以只有记录以1结尾的串和以0结尾的串就能求出答案；

完整代码

```#include<bits/stdc++.h>
using namespace std;
long long sol(string s,string s1,int n){
    string s2;int shu=0;
    for(int i=0;i<n;i++){
        if(s[i]!=s1[i]) {
            s2.push_back(s[i]);
            shu++;
        }

    }
    
    int c1=0,c0=0;
  
    for(int i=0;i<shu;i++){
        if(s2[i]=='1'&&c0!=0){
            c1++;
            c0--;
        }
        else if(s2[i]=='1'&&c0==0){
            c1++;
        }
        else if(s2[i]=='0'&&c1!=0){
            c1--;
            c0++;
        }
        else if(s2[i]=='0'&&c1==0){
            c0++;
        }
    }
   
    return c1+c0;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        string s;
        string s1,s2;
        cin>>n>>s;
        for(int i=1;i<=n;i++){
            if(i%2==1){
                s1.push_back('1');
                s2.push_back('0');
            }
           else{
               s1.push_back('0');
               s2.push_back('1');
           }
        }

        long long ans1=sol(s,s1,n);
        long long ans2=sol(s,s2,n);
        long long lans=min(ans1,ans2);
       cout<<lans<<'\n';
    }
    
    return 0;
}