Description

给定两个 0-1 串 \(S,T\)，每次操作你可以选择 \(S\) 的一个子序列，将其循环移位一格，求最少操作多少次能将 \(S\) 变成 \(T\)。

Solution

去掉那些已经相同的部分，对于剩下的，我们在一次操作中显然会交替选择那些 1 变 0 和 0 变 1 的位置，那么需要的最小次数就是一个区间内 1 变 0 和 0 变 1 的位置的数目差的绝对值的最大值。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

int n;
string s, t;
int d, mx, mn;

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> s >> t;
    for (int i = 0; i < n; i++)
        if (s[i] != t[i])
            d += s[i] - t[i], mx = max(mx, d), mn = min(mn, d);
    if (d == 0)
        cout << mx - mn;
    else
        cout << -1;
}