Educational Codeforces Round 97 (Rated for Div. 2)B. Reverse Binary Strings(反转子串)

地址：http://codeforces.com/contest/1437/problem/B

题意：

长度为N的只含0/1的子串，0的数目和1的数目均为n/2

操作：[L,R]内的子串反转

求使得整个串01交替的最少操作数

解析：

这种题，重在结果，而不是交替的过程

如果碰到00，那么找到下一个11，中间的0~1所有进行反转。

所以一个00，就需要消耗一个11来恢复01/10

所以记录一下00，11的数目c1,c2

取两者之间的最大值即可。

如果c1!=c2，结尾是可能存在001这种的，这个时候就不是成对消耗了。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
int m[111][111];
const int maxn =1e5 + 10;
int id[maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    { 
        int n;
        cin>>n;
        string s;
        cin>>s;
        int cnt=0;
        int c1=0,c2=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]==s[i+1]&&s[i]=='1')
            {    
                c1++;
            }
            if(s[i]==s[i+1]&&s[i]=='0')
            {
                c2++;
            }
        }
        
        cout<<max(c1,c2)<<endl;
    }
}