Submission #69855293

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        string s;
        cin>>n>>s;
        s = "$" + s;
        
        int pre1[n+5], pre0[n+5], suf1[n+5], suf0[n+5];
        pre1[0] = pre0[0] = suf1[n+1] = suf0[n+1] = 0;

        for(int i=1; i<=n; i++){
            pre1[i] = pre1[i-1];
            pre0[i] = pre0[i-1];

            if(s[i] == '0'){
                pre0[i] += 2;
                pre1[i]++;
            }
            else{
                pre0[i]++;
                pre1[i] += 2;
            }
        }

        for(int i=n; i>=1; i--){
            suf1[i] = suf1[i+1];
            suf0[i] = suf0[i+1];

            if(s[i] == '0'){
                suf0[i] += 2;
                suf1[i]++;
            }
            else{
                suf0[i]++;
                suf1[i] += 2;
            }
        }

        int ans = 1e9;
        for(int i=1; i<=n; i++){
            if(s[i] != s[i-1]){
                int l = i;
                while(i+1 <= n && s[i+1] == s[i]) i++;

                // cout<<l<<' '<<i<<" ";
                if(s[l] == '1'){
                    ans = min(ans, pre1[l-1] + suf1[i+1]);
                    // cout<<pre1[l-1]<<" "<<suf1[i+1]<<endl;
                }
                else{
                    ans = min(ans, pre0[l-1] + suf0[i+1]);
                    // cout<<pre0[l-1]<<" "<<suf0[i+1]<<endl;
                }
            }
        }

        cout<<ans<<endl;
    }
	return 0;
}

Submission Info

Judge Result