Educational cf 160的B题

Problem - B - Codeforces

找到最小操作次数，使得子串对应位与原来字符串对应位不相同。

交换是没有代价的，但是删除有代价。

首先复制两个一模一样的串，我们把下面作为固定串，然后对串中0和1的个数进行计数，由于我们最终的子串是向左对齐并依次与原串相反的，所以我们不妨从固定串的右边删起。先看下图

也就是说我们只需要删到固定串的0小于等于原串1的个数且固定串的1的个数小于原串0的个数，此时固定串的长度就是我们要找的长度，再用原串长度减去固定串的长度即可。

下面是代码

using i64 = long long;

void solve() {
    std::string s;
    std::cin >> s;

    std::array<int, 2> cnt{};
    for (auto x : s) {
        cnt[x - '0'] += 1;
    }
    int n = s.size();
    int ans = n;
    auto cur = cnt;
    for (int i = n - 1; i >= 0; i--) {
        if (cur[0] <= cnt[1] && cur[1] <= cnt[0]) {
            ans = n - 1 - i;
            break;
        }
        cur[s[i] - '0'] -= 1;
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}