算法
首先要明白翻转是什么意思:对前i头牛翻转,等价于把前i头牛的奇偶性互换
从前往后每2头牛分成一组,每一组牛有四种可能的情况:
GG,HH:这两种无论如何翻转,也不可能增加在偶数位置的G牛的情况,所以遇到这种情况我们直接忽略。
HG:这种排列是理想情况,我们要保证这种排列的数量不会变少
GH:我们的目标就是通过翻转,把这种排列变成HG
由于HG和GH叙述起来比较麻烦,所以我们对数组进行预处理:
两个两个的扫描s,遇到把”HG”这种组合记为0,把”GH”这种组合记为1。(”HH”和”GG”这两种组合直接忽略)
于是GH数组就变成了01数组,长度也大大缩短
我们的目标是所有的1变成0(即所有的”GH”变为”HG”),而对当前位置的前缀进行一次翻转可令当前位置及之前的所有位置进行一次01互换
根据连续1的位置,把这段1变成0所需的操作数也不同:如果连续一段1在最前端,则只需要一次,否则需要2次。如下图。
我们只需要数出来连续1的段数,然后×2,最后判断是不是有一段1在最前端,如果在则-1,即可得到答案。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
char s[N];
int a[N];
int main(){
cin >> n;
int t = 0;
cin >> s;
for(int i = 0; i < n; i += 2){
if(s[i] == 'G' && s[i + 1] == 'H'){
a[t ++] = 1;
}
else if(s[i] == 'H' && s[i + 1] == 'G') a[t ++] = 0;
}
int cnt = 0, i = 0;
while (i < t){
if(a[i ++] == 1){
while(i < t && a[i ++] == 1);
cnt ++;
}
}
int res = cnt * 2;
if(a[0] == 1)res --;
cout << res << endl;
return 0;
}