P6982: 照片拍摄

---

【题目描述】

【题目描述】
迫切希望在郡县集市上赢得最佳奶牛摄影师的 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-铜-公开赛 

咻咻~

提交答案 状态 返回