题目:AcWing 4440.照相

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//ACW4440 take cow photo
#include<iostream>
using namespace std;
const int N=2*1e5+10;

// 由于牛的总数为偶数,且每次翻转的牛的数量总取前偶数个
// 对于每次输入,对其进行两两一组的分组
// 对于组别GH,需要对其进行翻转,让其变为HG,因为翻转后会破坏前面已经符合题意的前缀
// 所以需要对其前缀进行翻转维护前缀的正确性
// 对于组别GG,HH,直接忽略即可

int c[N];

int main()
{
    int n;
    cin>>n;
    string s; 
    cin >> s;
    
    int ans=0;//翻转次数
    int flag=0;
    
    for(int i=0;i<n;i+=2)
        if(s[i]=='G'&&s[i+1]=='H') ans+=flag==2,flag=1;//GH情况,如果前面是GH,则先放着不管,攒着一起翻转前缀
        else if(s[i]=='H'&&s[i+1]=='G') ans+=flag==1,flag=2;//HG情况,如果前面也是GH的情况,则需要处理前面的前缀了
    
    if(flag==1) ans++;
    
    cout<<ans<<endl;
    return 0;
}