题解

想要有解，必须满足 \(1\) 的数量与 \(0\) 的数量的差的绝对值 \(\le 1\).

那么如果给定字符串 \(0\) 的数量大于 \(1\) 的数量，最后结果即应为 \("0101...0"\);那么如果给定字符串 \(1\) 的数量大于 \(0\) 的数量，最后结果即应为 \("1010...1"\);如果数量相等，最后结果为 \("0101...01"\) 或者 \("1010...10"\)，选择两种操作次数中最小的即可。

现在问题就转化成了，给定初始字符串 \(s\) 和目标字符串 \(t\) ，如何只通过交换在最小次数内由 \(s\) 变为 \(t\) .

可以发现，一次交换操作会将一个字符移动一个位置，如果想把一个字符从位置 \(i\) 移动到 \(j\)，那么所需要交换的次数即为 \(abs(i-j)\).

将所有 \(1\) 移动到对应位置后，所有 \(0\) 自然也移动到对应位置了，所以只需要每个\(1\)的 \(abs(i-j)\)并将其求和即可。

那么如何选择对应的位置使得结果最小呢？按顺序对应即可，也就是 \(s\) 中第一个 \(1\) 的位置要移动到的位置为 \(t\) 中第一个 \(1\) 的位置， \(s\) 中第二个 \(1\) 的位置要移动到的位置为 \(t\) 中第二个 \(1\) 的位置...

示例代码

typedef long long LL;
LL trans(string s, string t)
{
    int i=0, j=0;
    LL res = 0;
    
    for(int i=0; i<s.size(); i++)
    {
        while(j<t.size() && t[j] != '1') j++;
        
        if(s[i] == '1')
        {
            res += abs(i-j);
            j++;
        }
    }
    
    return res;
}
void Solve()
{
    string str;
    cin >> str;
    
    int zero = 0;
    int one = 0;
    int n = str.size();
    
    for(int i=0; i<n; i++)
    {
        if(str[i] == '0')   zero++;
        else    one++;
    }
    
    string tar;
    LL res;
    if(zero == one)
    {
        for(int i=0; i<n/2; i++)
            tar += "10";
            
        res = trans(str, tar);
        
        reverse(tar.begin(), tar.end());
        
        res = min(res, trans(str, tar));
    }
    
    else if(zero > one)
    {
        for(int i=0; i<n/2; i++)
            tar += "01";
            
        tar.push_back('0');
        
        res = trans(str, tar);
    }
    else
    {
        for(int i=0; i<n/2; i++)
            tar += "10";
            
        tar.push_back('1');
        
        res = trans(str, tar);
    }
    
    cout << res << endl;
}