← 返回题目列表

AtCoder · awc0060_b

B. 失踪调查和团队划分

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥正试图分割 N 学生分成两队:红队和白队。他提前进行了一项调查,要求每个学生在一张纸上写下自己喜欢的球队。

然而,咖啡洒在了一些调查论文上,导致一些回复无法阅读。不可读的响应记录为 ?,并且无法确定他们最初说的是“红色”还是“白色”。

每个学生的回答都由一个字符表示: R (更喜欢红队), W (首选白队),或 ? (不可读)。

高桥想要独立替换每个不可读的响应(?) 与任一 R (更喜欢红队)或 W (优先选择白队),以尽量减少最终红队支持者与白队支持者人数之间的绝对差值。

求当红队支持者数量和白队支持者数量之间的最小可能绝对差值 ?被最佳替换。如果没有 ?s,简单地根据响应计算绝对差。

约束

  • 1 \leq N \leq 10^5
  • S_i 是其中之一 R, W,或 ? (1 \leq i \leq N)

输入

N
S_1
S_2
\vdots
S_N
  • 第一行包含一个整数 N 代表学生人数。
  • 对于 i = 1, 2, \dots, N, (1 + i)- 第行包含单个字符 S_i 代表响应 i第一个学生。 S_i 是其中之一 R, W,或 ?.

输出

在一行上打印红队支持者数量和白队支持者数量之间的最小可能绝对差。


示例输入 1

5
R
W
?
R
?

示例输出 1

1

示例输入 2

8
R
W
?
R
?
?
R
?

示例输出 2

0

示例输入 3

10
R
R
W
?
R
?
R
R
?
W

示例输出 3

0