寒假算法基础集训营3 C题题解
宙天
https://ac.nowcoder.com/acm/contest/120563/A
首先可知答案只会出现01010和10101。所以讨论两种情况，对每种情况，将不满足的字符提出来新组成一个字符串，接着通过贪心的方式计数剩余未匹配的0和1然后成对删除不匹配的0和1即可，最后记得取两种情况的最小值。
附本人ac码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define mod 998244353
const ll N=1e6+10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string s;
cin>>s;
int ans=1e9;
for(int i=0;i<=1;i++)
{
string t;
for(int j=0;j<n;j++)
{
if(s[j]-'0'!=((j&1)^i))
{
t+=s[j];
}
}
vector<int>cnt(2);
for(auto c:t)
{
int x=c-'0';
if(cnt[1-x])
{
cnt[1-x]--;
cnt[x]++;
}
else
{
cnt[x]++;
}
}
ans=min(ans,cnt[0]+cnt[1]);
}
cout<<ans<<endl;
}
return 0;
}
