CF1776G Another Wine Tasting Event

在第一次成功举办品酒会后，Gabriella 被邀请组织第二届品酒活动。现在有 $2n-1$ 瓶酒排成一排，每瓶酒要么是红葡萄酒，要么是白葡萄酒。 这一次，Gabriella 已经决定了所有酒瓶的类型和顺序。酒的类型由一个长度为 $2n-1$ 的字符串 $s$ 表示。对于每个 $1 \le i \le 2n-1$，如果第 $i$ 瓶是红葡萄酒，则 $s_i = \texttt{R}$；如果是白葡萄酒，则 $s_i = \texttt{W}$。 恰好有 $n$ 位品酒评论家受邀参加，评论家编号为 $1$ 到 $n$。和去年一样，每位评论家 $j$ 想要品尝一段连续的酒瓶，即第 $a_j,\, a_j+1,\, \dots,\, b_j$ 瓶，其中 $1 \le a_j \le b_j \le 2n-1$。此外，他们还有如下额外要求： - 每位评论家都要品尝至少 $n$ 瓶酒，即 $b_j - a_j + 1 \ge n$； - 不能有两位评论家品尝完全相同的酒瓶区间，即如果 $j \ne k$，则 $a_j \ne a_k$ 或 $b_j \ne b_k$。 Gabriella 知道，由于活动举办地靠近意大利海岸，评论家们对白葡萄酒格外感兴趣，而对红葡萄酒不太在意（毕竟白葡萄酒更适合搭配海鲜）。因此，为了公平起见，她希望所有评论家品尝到的白葡萄酒数量相同。 请你帮助 Gabriella 找到一个整数 $x$（$0 \le x \le 2n-1$），使得存在一种有效的区间分配方案，使每位评论家都恰好品尝到 $x$ 瓶白葡萄酒。可以证明，至少存在一个这样的 $x$。如果有多个答案，输出任意一个即可。

第一行包含一个整数 $n$（$1 \le n \le 10^6$），其中 $2n-1$ 是酒瓶的数量，$n$ 是评论家的数量。 第二行包含一个长度为 $2n-1$ 的字符串 $s$，表示酒瓶的排列顺序——第 $i$ 个字符 $s_i$（$1 \le i \le 2n-1$）为 $\texttt{R}$ 表示红葡萄酒，为 $\texttt{W}$ 表示白葡萄酒。

输出一个整数 $x$，表示每位评论家将品尝到的白葡萄酒数量。 可以证明至少存在一个解。如果有多个解，输出任意一个即可。

在第一个样例中，有 $5$ 位评论家和 $2 \cdot 5 - 1 = 9$ 瓶酒。一个可行的区间分配方案，使每位评论家都品尝到 $2$ 瓶白葡萄酒如下：$[2, 6]$，$[1, 6]$，$[4, 8]$，$[1, 5]$，$[3, 7]$。注意所有区间都包含至少 $5$ 瓶酒。 在第二个样例中，有 $1$ 位评论家和 $2 \cdot 1 - 1 = 1$ 瓶酒。唯一可能的区间是 $[1, 1]$，此时 $x = 0$。 由 ChatGPT 4.1 翻译