← 返回题目列表

Codeforces · 1515/D

D. 凤凰和袜子

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

为了满足他对搭配袜子的热爱,菲尼克斯把他的 $$$n$$$ 袜子($$$n$$$ 是偶数)带到了袜子店。他的每只袜子都有一个颜色 $$$c_i$$$ 并且是左袜子或右袜子。

Phoenix 可以向袜子店支付 1 美元来执行以下任一操作:

- 将袜子重新着色为任意颜色 $$$c'$$$ $$$(1 \le c' \le n)$$$
- 将左袜子变成右袜子
- 将右袜子变成左袜子

袜子存储可以执行这些更改中的每一个任意次数。请注意,当左袜子变成右袜子时,其颜色不会改变,反之亦然。

一双配套的袜子是左右一只袜子颜色相同。 Phoenix 制造 $$$n/2$$$ 匹配对的最低成本是多少?每只袜子必须完全匹配。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$l$$$ 和 $$$r$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n$$$ 是偶数; $$$0 \le l, r \le n$$$; $$$l+r=n$$$) — 袜子总数,以及分别是左袜子和右袜子的数量。

下一行包含 $$$n$$$ 整数 $$$c_i$$$ ($$$1 \le c_i \le n$$$) — 袜子的颜色。第一个 $$$l$$$ 袜子是左袜子,而接下来的 $$$r$$$ 袜子是右袜子。

保证所有测试用例的 $$$n$$$ 总和不会超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - Phoenix 生成 $$$n/2$$$ 匹配对的最低成本。每只袜子必须完全匹配。

示例

输入 #1

4
6 3 3
1 2 3 2 2 2
6 2 4
1 1 2 2 2 2
6 5 1
6 5 4 3 2 1
4 0 4
4 4 4 3

输出 #1

2
3
5
3

注意

在第一个测试用例中,Phoenix 可以向以下对象支付 $$$2$$$ 美元:

- 将袜子 $$$1$$$ 重新着色为 $$$2$$$
- 将袜子 $$$3$$$ 重新着色为 $$$2$$$

在第二个测试用例中,Phoenix 可以向以下对象支付 $$$3$$$ 美元:

- 将袜子$$$6$$$从右袜子变成左袜子
- 将袜子 $$$3$$$ 重新着色为 $$$1$$$
- 将袜子 $$$4$$$ 重新着色为 $$$1$$$