310053: CF1776G. Another Wine Tasting Event
Memory Limit：256 MB
Time Limit：0 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Another Wine Tasting Event
题目描述
After the first successful edition, Gabriella has been asked to organize a second wine tasting event. There will be $ 2n - 1 $ bottles of wine arranged in a row, each of which is either red wine or white wine. This time, Gabriella has already chosen the type and order of all the bottles. The types of the wines are represented by a string $ s $ of length $ 2n - 1 $ . For each $ 1 \le i \le 2n - 1 $ , it holds that $ s_i = \texttt{R} $ if the $ i $ -th bottle is red wine, and $ s_i = \texttt{W} $ if the $ i $ -th bottle is white wine. Exactly $ n $ critics have been invited to attend. The critics are numbered from $ 1 $ to $ n $ . Just like last year, each critic $ j $ wants to taste an interval of wines, that is, the bottles at positions $ a_j, \, a_j + 1, \, \dots, \, b_j $ for some $ 1 \le a_j \le b_j \le 2n - 1 $ . Moreover, they have the following additional requirements: - each of them wants to taste at least $ n $ wines, that is, it must hold that $ b_j - a_j + 1 \ge n $ ; - no two critics must taste exactly the same wines, that is, if $ j \ne k $ it must hold that $ a_j \ne a_k $ or $ b_j \ne b_k $ . Gabriella knows that, since the event is held in a coastal region of Italy, critics are especially interested in the white wines, and don't care much about the red ones. (Indeed, white wine is perfect to accompany seafood.) Thus, to ensure fairness, she would like that all critics taste the same number of white wines. Help Gabriella find an integer $ x $ (with $ 0 \le x \le 2n - 1 $ ) such that there exists a valid assignment of intervals to critics where each critic tastes exactly $ x $ white wines. It can be proved that at least one such $ x $ always exists.输入输出格式
输入格式
The first line contains the integer $ n $ ( $ 1 \le n \le 10^6 $ ) — where $ 2n - 1 $ is the number of bottles, and $ n $ is the number of critics. The second line contains a string $ s $ of length $ 2n - 1 $ that represents the arrangement of the wines — the $ i $ -th character of $ s $ ( $ 1 \le i \le 2n - 1 $ ) is $ \texttt{R} $ for a red wine and $ \texttt{W} $ for a white wine.
输出格式
Print an integer $ x $ — the number of white wines that each critic will taste. It can be proved that at least one solution exists. If multiple solutions exist, any of them will be accepted.
输入输出样例
输入样例 #1
5
RWWRRRWWW输出样例 #1
2输入样例 #2
1
R输出样例 #2
0说明
In the first sample, there are $ 5 $ critics and $ 2 \cdot 5 - 1 = 9 $ bottles of wine. A possible set of intervals that makes each critic taste $ 2 $ white wines is the following: $ [2, 6], $ $ [1, 6], $ $ [4, 8], $ $ [1, 5], $ $ [3, 7] $ . Note that all intervals contain at least $ 5 $ bottles. In the second sample, there is $ 1 $ critic and $ 2 \cdot 1 - 1 = 1 $ bottle of wine. The only possible interval is $ [1, 1] $ , which gives $ x = 0 $ .Input
题意翻译
给出一个长为 $2\times N-1$ 的字符序列，只由 `R` 和 `W` 组成。 你需要在这个字符串中选出 $N$ 个长为 $N$ 的区间，每个区间中的 `W` 的数量必须 $=x$。 请求出满足所有条件的情况下，$x$ 的最小值。Output
**题目描述**
在第一次成功举办品酒会之后，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$，表示酒的排列 —— $s$ 的第 $i$ 个字符（$1 \le i \le 2n - 1$）是红酒的 $\texttt{R}$ 和白酒的 $\texttt{W}$。
**输出格式**
打印一个整数 $x$ —— 每位品酒师将品尝的白酒数量。
可以证明至少存在一个解。如果存在多个解，则可以接受其中任何一个。
**输入输出样例**
**输入样例 #1**
```
5
RWWRRRWWW
```
**输出样例 #1**
```
2
```
**输入样例 #2**
```
1
R
```
**输出样例 #2**
```
0
```
**说明**
在第一个样例中，有 $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$。**题目描述** 在第一次成功举办品酒会之后，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$，表示酒的排列 —— $s$ 的第 $i$ 个字符（$1 \le i \le 2n - 1$）是红酒的 $\texttt{R}$ 和白酒的 $\texttt{W}$。 **输出格式** 打印一个整数 $x$ —— 每位品酒师将品尝的白酒数量。 可以证明至少存在一个解。如果存在多个解，则可以接受其中任何一个。 **输入输出样例** **输入样例 #1** ``` 5 RWWRRRWWW ``` **输出样例 #1** ``` 2 ``` **输入样例 #2** ``` 1 R ``` **输出样例 #2** ``` 0 ``` **说明** 在第一个样例中，有 $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$。
在第一次成功举办品酒会之后，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$，表示酒的排列 —— $s$ 的第 $i$ 个字符（$1 \le i \le 2n - 1$）是红酒的 $\texttt{R}$ 和白酒的 $\texttt{W}$。
**输出格式**
打印一个整数 $x$ —— 每位品酒师将品尝的白酒数量。
可以证明至少存在一个解。如果存在多个解，则可以接受其中任何一个。
**输入输出样例**
**输入样例 #1**
```
5
RWWRRRWWW
```
**输出样例 #1**
```
2
```
**输入样例 #2**
```
1
R
```
**输出样例 #2**
```
0
```
**说明**
在第一个样例中，有 $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$。**题目描述** 在第一次成功举办品酒会之后，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$，表示酒的排列 —— $s$ 的第 $i$ 个字符（$1 \le i \le 2n - 1$）是红酒的 $\texttt{R}$ 和白酒的 $\texttt{W}$。 **输出格式** 打印一个整数 $x$ —— 每位品酒师将品尝的白酒数量。 可以证明至少存在一个解。如果存在多个解，则可以接受其中任何一个。 **输入输出样例** **输入样例 #1** ``` 5 RWWRRRWWW ``` **输出样例 #1** ``` 2 ``` **输入样例 #2** ``` 1 R ``` **输出样例 #2** ``` 0 ``` **说明** 在第一个样例中，有 $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$。