CF2103B题解

//仅供个人学习记录 
#include<iostream>
using namespace std;
int main() {
    //题目分析：
    //代价是字符串长度（按下的次数）加上切换的次数
    //题目的目的是为了减少切换的次数 
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        string s;
        int n;
        cin >> n >> s;
        int change = 0;
        //此时要判断首位是0还是1 可以直接用if判断 也可以在字符串最前面加1个0
        //此时长度是n+1 那如果这样的话直接遍历j和j-1项就好了
        s = '0' + s;
        for (int j = 1; j <= n; j++) {
            if (s[j] != s[j - 1]) {
                change++;
            }
        }
        //此时开始分类讨论
        // 注：n就是原本的长度 不需要在因为最前面的0多减1
        //如果变换就一次 例 10000 7次（变换2次） 00001 6次 省去变1 变回来 00100 和10000是一样的
        //所以如果变换一次可以发现 不需要换 就是最优解 
        if (change <= 1) cout << n + change << endl;
        //然后看两次变换的 10000 01000 可以通过变换 变成1次00001 这个也是最优解 比如 00100 00001 
        else if(change == 2) cout << n + change - 1 << endl;
        //然后看3次变换的 01001 10001 都可以通过改变顺序 变成 00011 这样就只剩一次变换 
        //本题通过读题可以发现 最多就节约两次 （旋转的首尾各节约一次 ）
        else if(change>=3) cout << n + change - 2 << endl;
        //change = 0;//重置
    }
    return 0;
}