题解 | #小红的元素交换#

是原题，有需求请移步这道题 并查找其题解

本题解讲 。

首先是这类问题经典做法，把所有置换找出来。以图论形式而言，就是将每个点通过 而形成的若干个环找到。

然后就是所有置换内部处理。如果置换内有两种颜色的元素，那么它必然可以调整操作顺序，使得操作数为 。反之则需要与其他置换进行联动。

单色置换之间操作显然，随便交换一对元素，当双色置换做一遍，再换回去即可。

答案即 , 为置换数量， 分别表示两种颜色的单色置换数量。

核心代码:

void solve()
{
    int n; string s;
    cin >> n;
    vector<int> a(n+1);
    vector<bool> vis(n+1);
    For(i,1,n) cin >> a[i];
    cin >> s; s = '#' + s;
    int cntr = count(s.begin(),s.end(),'R');
    if(cntr == 0 || cntr == n)
    {
        cout << (is_sorted(a.begin()+1,a.end())?"0":"-1") << '\n';
        return; 
    }
    int cr(0), cw(0), ans(0);
    For(i,1,n)
    {
        if(vis[i]) continue;
        int u = i, cnt = 0;
        bool fr(false), fw(false);
        while(!vis[u])
        {
            ++cnt; vis[u] = true;
            fr |= (s[u]=='R');
            fw |= (s[u]=='W');
            u = a[u]; 
        }
        ans += cnt-1;
        if(cnt > 1)
        {
            if(!fw) ++cr;
            else if(!fr) ++cw;    
        }        
    }
    cout << ans + 2*max(cr,cw) << '\n';
}