AT_arc097_c.[ARC097E] Sorted and Sorted

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $2N$ 个球排成一列，其中白球和黑球各 $N$ 个，每个球上写有 $1$ 到 $N$ 的整数，每个数字各出现一次。第 $i$ 个球上写的数字为 $a_i$ ，颜色为 $c_i$ 。当 $c_i = \texttt{W}$ 时表示该球为白色，当 $c_i = \texttt{B}$ 时表示该球为黑色。

高桥君有如下目标：

对于任意满足 $1 \leq i < j \leq N$ 的整数对 $(i, j)$ ，写有 $i$ 的白球必须在写有 $j$ 的白球的左侧。
对于任意满足 $1 \leq i < j \leq N$ 的整数对 $(i, j)$ ，写有 $i$ 的黑球必须在写有 $j$ 的黑球的左侧。

为达成目标，高桥君可以进行如下操作：

交换相邻的两个球。

请你求出，为达成目标所需的最小操作次数。

输入格式

输入通过标准输入给出，格式如下：

$N$ $c_1$ $a_1$ $c_2$ $a_2$ $\cdots$ $c_{2N}$ $a_{2N}$

输出格式

输出达成目标所需的最小操作次数。

输入输出样例

输入#1
```
3
B 1
W 2
B 3
W 1
W 3
B 2
```
输出#1
```
4
```
输入#2
```
4
B 4
W 4
B 3
W 3
B 2
W 2
B 1
W 1
```
输出#2
```
18
```

输入#3

9
W 3
B 1
B 4
W 1
B 5
W 9
W 2
B 6
W 5
B 3
W 8
B 9
W 7
B 2
B 8
W 4
W 6
B 7

输出#3

说明/提示

限制

$1 \leq N \leq 2000$
$1 \leq a_i \leq N$
$c_i = \texttt{W}$ 或 $c_i = \texttt{B}$
若 $i \neq j$ ，则 $(a_i, c_i) \neq (a_j, c_j)$

样例解释 1

例如如下操作可以在 $4$ 次内完成目标：

交换黑色 $3$ 和白色 $1$
交换白色 $1$ 和白色 $2$
交换黑色 $3$ 和白色 $3$
交换黑色 $3$ 和黑色 $2$

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页