是原题,有需求请移步这道题 并查找其题解
本题解讲 。
首先是这类问题经典做法,把所有置换找出来。以图论形式而言,就是将每个点通过 而形成的若干个环找到。
然后就是所有置换内部处理。如果置换内有两种颜色的元素,那么它必然可以调整操作顺序,使得操作数为 。反之则需要与其他置换进行联动。
单色置换之间操作显然,随便交换一对元素,当双色置换做一遍,再换回去即可。
答案即 ,
为置换数量,
分别表示两种颜色的单色置换数量。
核心代码:
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';
}