C-有趣的家庭菜园 3_JOI2019-Final比赛真题

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

译自 JOI 2019 Final T3「たのしいたのしいたのしい家庭菜園 / Growing Vegetable is Fun 3」

家庭菜园专家JOI先生在他的家庭菜园中种植了一种叫Joy草的植物。在他的菜园里，有N个花盆自东向西摆放，编号分别为 $1, \ldots,N$ 。每个花盆中有一株Joy草。
春天到了，JOI先生注意到Joy草如他期望地长出了各种颜色的叶子，但他也发现Joy草的生长速度没有他期望的那么快。他查阅了书籍，找到了草的以下特点：

Joy草有三种品种，分别会长出红色、绿色和黄色的叶子。
如果两株同一颜色的Joy草紧密相邻，它们的生长速度就会减慢。

因此，JOI先生决定重新摆放花盆，使得没有两株相邻的Joy草颜色相同。
花盆非常沉重，因此JOI先生每次只能交换相邻的两个花盆。形式化的说，JOI先生每次操作可以选择一个 $i(1 \le i \lt N)$ ，然后交换花盆i和花盆i+1。
请编写一个程序，计算最少的交换次数。

输入描述:

从标准输入中读取数据。
第一行一个整数N。
接下来一行一个长度为N的字符串S，每个字符为R,G,Y中的一个，表示Joy草的颜色。

输出描述:

输出数据到标准输出中。
输出一行一个整数，表示完成目标所需的最少操作次数。如果无解，输出-1。

示例1

输入

复制

5
RRGYY

输出

复制

说明

一种合法的方案是：
第一步：交换第三个花盆和第四个花盆。
第二步：交换第二个花盆和第三个花盆。
在交换完成后，Joy草的颜色序列为RYRGY。
可以证明JOI先生不能用少于2次交换完成目标，所以答案为2。

示例2

输入

复制

6
RRRRRG

输出

复制

-1

说明

在这个样例中，无论如何操作，都不能使任意两株相邻 Joy 草颜色不同。

示例3

输入

复制

20
YYGYYYGGGGRGYYGRGRYG

输出

复制

备注:

对于所有输入数据，有。

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/3012