洛谷P8266

题意

$(2 \le$ 长度 $\le 2 \times 10^5)$。

给定一个偶数长度的 H 和 G 组成的排列，每次可以将偶数长度的前缀进行翻转。

求在偶数下标上的 G 的数量尽量多的情况下，使翻转次数尽量的少。

思路

重点注意 偶数 这个词

因为是将偶数长度的前缀进行翻转，所以可以将两个相邻的字符看做一坨，当一坨中的两个字符不同，设这一坨为 0 或 1（因为要么是 HG，要么是 GH，两种情况），若相同，就舍去，即不管这一坨。

要注意最后一个不同的一坨。

然后这道绿题就变成了硬币翻转这样一道红题：将一个 01 串进行前缀翻转，使都为 1。（若 GH 为 0，要都为 1，若 GH 为 1，要都为 0）。

最后只需要模拟即可，模拟就每个前缀区间依次翻转。

可以分析如下样例：

如 0000111001，即排列为 GH GH GH GH HG HG HG GH GH HG。

• 第一次翻转：1111111001
• 第二次翻转：0000000001
• 第三次翻转：1111111111

如 00001110010, 即排列为 GH GH GH GH HG HG HG GH GH HG GH。

• 第一次翻转：11111110010
• 第二次翻转：00000000010
• 第三次翻转：11111111110
• 第四次翻转：00000000000
• 第五次翻转：11111111111

时空复杂度

时间复杂度 : $O(n)$。

空间复杂度 : $O(n)$。

代码如下

1.易看懂目的的

#include <bits/stdc++.h>

using namespace std;

int n, cnt = 0;
char a[200010];

int main(){
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  bool ooo = 0;
  for(int i = 1, j; i <= n; i = j){
    j = i + 2;
    if(a[i] != a[i + 1] && a[i] == 'G'){
      for( ; j <= n; j += 2){
        if(a[j] != a[j + 1] && a[j] == 'H'){
          break;
        }
      }
      cnt += 1 + ooo;
    }else if(a[i] != a[i + 1] && a[i] == 'H'){
      ooo = 1;
    }
  }
  cout << cnt;
  return 0;
}

2.简化后的

#include <bits/stdc++.h>

using namespace std;

int n, cnt = 0;
char a[200010], l = 'A';

int main(){
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 1; i <= n; i += 2){    // 两两为一组计算
    if(a[i] != a[i + 1]){
      cnt += a[i] != l, l = a[i];    // 求有多少个连续且相同的连通块 
    }
  }
  cout << cnt - (l == 'H'); // 当数据为 1001，答案要减去 1，因为最后的一个 1 的连通块被多余求解了 
  return 0;
}