#PU1227. USACO 2022 US Open Contest, Bronze — Problem 1. Photoshoot

    ID: 1624 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>USACO赛事:open22来源:usaco.orgscoring:equal_test_cases贪心字符串

USACO 2022 US Open Contest, Bronze — Problem 1. Photoshoot

USACO 2022 US Open Contest, Bronze — Problem 1. Photoshoot

题目描述

Farmer John, desperate to win the award for best cow photographer at the county fair, is trying to take the perfect photograph of his NN cows (2≤N≤2⋅1052 \leq N \leq 2\cdot 10^5, NN even). Farmer John owns cows of two potential breeds: Guernseys and Holsteins.
To make his photo as aesthetic as possible, he wants to line up his cows so that as many Guernseys are in even-numbered positions in the line as possible (the first position in the line is an odd position, the next is an even position, and so on). Due to his lack of strong communication with his cows, the only way he can achieve his goal is by asking even length "prefixes" of his cows to reverse themselves (a prefix consists of the range of cows from the first cow up to the jjth cow for some position jj). Please count the minimum number of reversals required for Farmer John to achieve his goal.

输入格式

The first line of input contains the value of NN. The second line contains a string of length N,N, specifying the initial ordering of the cows from left to right. Each 'H' represents a Holstein, while each 'G' represents a Guernsey.

输出格式

(见题面原文)

数据范围

Test cases 2-6 satisfy N≤1000N\le 1000. Test cases 7-11 satisfy no additional constraints. Problem credits: Aryansh Shrivastava

样例

样例 1

14
GGGHGHHGHHHGHG
1
In this example, it suffices to reverse the prefix consisting of the first six
cows.
GGGHGHHGHHHGHG (Before)
-> HGHGGGHGHHHGHG (After)
Before the reversal, four Guernseys were at even positions. After the reversal,
six Guernseys are at even positions. It is impossible for there to be more than
six Guernseys at even positions.