题目描述

迫切希望在郡县集市上赢得最佳奶牛摄影师的农夫约翰正在尝试为他的 N
头奶牛拍摄一张完美的照片。

农夫约翰拥有两种品种的奶牛：更赛牛（Guernsey）和荷斯坦牛（Holstein）。

为了使他的照片尽可能地艺术，他想把他的奶牛排成一排，使得尽可能多的更赛牛处于队列中的偶数位置（队列中的第一个位置是奇数位置，下一个是偶数位置，以此类推）。

由于他与他的奶牛缺乏有效的沟通，他可以达到目的的唯一方法是让他的奶牛的偶数长的「前缀」进行反转（一个前缀指的是对于某个位置 j
，从第一头奶牛到第 j
头奶牛范围内的所有奶牛）。

请计算农夫约翰达到目的所需要的最小反转次数。

输入格式
输入的第一行包含 N
的值。

第二行包含一个长为 N
的字符串，给出初始时所有奶牛从左到右的排列方式。每个 H 代表一头荷斯坦牛，每个 G 代表一头更赛牛。

输出格式
输出一行，包含达到目的所需要的最小反转次数。

数据范围
2≤N≤2×105，N为偶数。

样例

14
GGGHGHHGHHHGHG

输出样例

1

C++ 代码

/*偶数长度的奶牛数量以及只能翻转第偶数个的前缀和，可以两个分一组
GG GH GH HG HH HG HG  // GG HH 不影响计算，将GH 映射为1，GH 为0 ，GG,HH不要
则只需将  GH （1） - >  HG (0)
原样例转化为
x  1  1  0  x  0  0 ，即11000//由于翻转到最后肯定能获得0000000......；
（010可为110->000; 101 -> 001 -> 111->000）最后总能得到0000000.....;
每一个不同10或者01都要翻转至少一次才能使前后串相同（即变成11或者00），
其中如果是以1结尾则还需再翻转一次使11->00； 以1结尾有01，11两种，其中01会被前面的操作处理成11           
综上所诉，得到如下代码
*/
#include<iostream>
using namespace std;
const int N = 2e5+10;
int n,m;//m为w数组下标
char str[N];//存储字符串
int w[N];//存储01串并且由于初始化内部元素全部为0,以1结尾时也会出现10000000，不用特殊处理1结尾了
int main()
{
    int ans = 0;
    scanf("%d%s",&n,str+1);
    for(int i = 1; i <= n+1;i+=2)//一组一组的来遍历，由于下标从1开始所以存储的n个字符下标是1到n+1
    {
        if(str[i] != str[i+1]) // 不是GG,HH
        {
            if(str[i] == 'G') w[++m] = 1;//GH
            else w[++m] = 0;//HG
        }
    }
    for(int i = 1; i <= m; i++)
    {
        //cout<<w[i]<<" ";
        if(w[i] != w[i+1]) ans++;
    }
   cout << ans;
}