寒假算法基础集训营3 C题题解

首先可知答案只会出现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;
}