问题描述
对于这样一串数字,他只存在0或者1,我们每次都能将一个0变成1又或者把一个1变成0,先需要我们将这串数字变成前半部分是0后半部分是1(或者全是0又或者全是1),至少我们需要变化多少次?
输入格式
第一行输入需要变化N串数字(1<=N<=30)
随后的N行输入该串的长度 以及串;(1<=length<=2*10000)
输出格式
每行输出最少变化次数(输出完后需要换行)
输入样例
2
10
1100011011
4
1101
输出样例
3
1
#include<iostream>
using namespace std;
#define N 200000
#define MIN 100000
int dp[N]={0};
int main()
{
int n;
cin>>n;
while(n--){
string s;
int k,i,cnt,sum=0,min=MIN;
cin>>k;
cin>>s;
dp[0]=0;
for(cnt=0,i=0;i<k;i++){
if(s[i]-'0'==cnt%2)
dp[cnt]++;
else{
sum+=(cnt%2?0:dp[cnt]);
cnt++;
dp[cnt]=0;
i--;
}
}
sum+=(cnt%2?0:dp[cnt]);
for(i=0;i<=cnt;i++){
if(i%2)
sum+=dp[i];
else
sum-=dp[i];
if(sum<min)
min=sum;
}
if(min==MIN)
cout<<"0"<<endl;
else
cout<<min<<endl;
}
}