3677. [USACO22 Open Bronze]Photoshoot

【题目描述】

  迫切希望在郡县集市上赢得最佳奶牛摄影师的 $Farmer$ $John$ 正在尝试为他的 $N$ 头奶牛拍摄一张完美的照片（$2≤N≤2*10^5$，$N$ 为偶数）。

  $Farmer$ $John$ 拥有两种品种的奶牛：更赛牛（$Guernsey$）和荷斯坦牛（$Holstein$）。为了使他的照片尽可能地艺术，他想把他的奶牛排成一排，使得尽可能多的更赛牛处于队列中的偶数位置（队列中的第一个位置是奇数位置，下一个是偶数位置，以此类推）。由于他与他的奶牛缺乏有效的沟通，他可以达到目的的唯一方法是让他的奶牛的偶数长的「前缀」进行反转（一个前缀指的是对于某个位置 $j$，从第一头奶牛到第 $j$ 头奶牛范围内的所有奶牛）。

请计算 $Farmer$ $John$ 达到目的所需要的最小反转次数。

【输入格式】

输入的第一行包含 $N$ 的值。

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

【输出格式】

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

【样例输入】

14
GGGHGHHGHHHGHG

【样例输出】

1

【样例说明】

在这个例子中，只需反转由前六头奶牛组成的前缀即可。

GGGHGHHGHHHGHG （反转前）

->

HGHGGGHGHHHGHG （反转后）

在反转之前，四头更赛牛处于偶数位置。反转后，六头更赛牛处于偶数位置。不可能使得超过六头更赛牛处于偶数位置。

【数据规模与约定】

测试点$2 - 6$，满足$N≤1000$;

测试点$7 - 11$，没有额外限制;

【来源】

USACO 2022 OPEN CONTEST BRONZE Problem 1 Photoshoot

供题：Aryansh Shrivastava