GirlsAndBoys
TCO10 Qual 1 · 2010-04-11 · by soul-net
TCO10 Qual 1 · 2010-04-11 · by soul-net · Greedy
Problem Statement
Problem Statement
There are N students standing in a single row, one next to the other, numbered 0 to N-1 from left to right. Your goal is to minimize the number of adjacent pairs where one student is a boy and the other is a girl. More precisely, you want to minimize the number of values i, 0 <= i < N-1, where student i and student i+1 are of different genders.
You are given the current arrangement as aString row, where the i-th character is 'G' if student i is a girl, and 'B' if student i is a boy. In a single move, you can choose two adjacent students and swap their positions. Return the minimum number of moves required to achieve your goal.
You are given the current arrangement as a
Constraints
- row will contain between 1 and 50 characters, inclusive.
- Each character in row will be 'G' or 'B'.
Examples
0)
"GGBBG" Returns: 2
You can swap the rightmost girl with the two boys (one after the other) to get "GGGBB", with a minimum of only 1 pair of adjacent students of different gender.
1)
"BBBBGGGG" Returns: 0
There is already a single pair of adjacent students of different gender, and there is no arrangement without such pairs at all, so the best solution is to swap nothing.
2)
"BGBGBGBGGGBBGBGBGG" Returns: 33
3)
"B" Returns: 0
With only one student, there is not much swapping to do.
4)
"G" Returns: 0
Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class GirlsAndBoys with a public method int sortThem(string row) · 77 test cases · 2 s / 256 MB per case