Phoenix and Socks

题意翻译

### 题目描述 Phoenix 有 $n$ 只袜子（保证 $n$ 为偶数），其中 $l$ 只左袜子，$r$ 只右袜子。每只袜子有颜色 $c_i$ （$1 \le c_i \le n$） 。 现在你有三个操作，每个操作代价为 $1$： 1.将某只袜子颜色换为 $c'$，（$1 \le c' \le n$） 2.将左袜子变为右袜子 3.将右袜子变为左袜子 求使所有袜子匹配成 $\frac n2$ 对袜子（即，颜色相同，且左右袜子各一）的代价。 ### 输入格式 第一行一个数 $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$），为 $n$ 只袜子的颜色。其中，前 $l$ 个数为左袜子，后 $r$ 个数为右袜子。

题目描述

To satisfy his love of matching socks, Phoenix has brought his $ n $ socks ( $ n $ is even) to the sock store. Each of his socks has a color $ c_i $ and is either a left sock or right sock. Phoenix can pay one dollar to the sock store to either: - recolor a sock to any color $ c' $ $ (1 \le c' \le n) $ - turn a left sock into a right sock - turn a right sock into a left sock The sock store may perform each of these changes any number of times. Note that the color of a left sock doesn't change when it turns into a right sock, and vice versa. A matching pair of socks is a left and right sock with the same color. What is the minimum cost for Phoenix to make $ n/2 $ matching pairs? Each sock must be included in exactly one matching pair.

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The first line of each test case contains three integers $ n $ , $ l $ , and $ r $ ( $ 2 \le n \le 2 \cdot 10^5 $ ; $ n $ is even; $ 0 \le l, r \le n $ ; $ l+r=n $ ) — the total number of socks, and the number of left and right socks, respectively. The next line contains $ n $ integers $ c_i $ ( $ 1 \le c_i \le n $ ) — the colors of the socks. The first $ l $ socks are left socks, while the next $ r $ socks are right socks. It is guaranteed that the sum of $ n $ across all the test cases will not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print one integer — the minimum cost for Phoenix to make $ n/2 $ matching pairs. Each sock must be included in exactly one matching pair.

输入输出样例

输入样例 #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

说明

In the first test case, Phoenix can pay $ 2 $ dollars to: - recolor sock $ 1 $ to color $ 2 $ - recolor sock $ 3 $ to color $ 2 $ There are now $ 3 $ matching pairs. For example, pairs $ (1, 4) $ , $ (2, 5) $ , and $ (3, 6) $ are matching.In the second test case, Phoenix can pay $ 3 $ dollars to: - turn sock $ 6 $ from a right sock to a left sock - recolor sock $ 3 $ to color $ 1 $ - recolor sock $ 4 $ to color $ 1 $ There are now $ 3 $ matching pairs. For example, pairs $ (1, 3) $ , $ (2, 4) $ , and $ (5, 6) $ are matching.

题意翻译

### 题目描述 Phoenix 有 $n$ 只袜子（保证 $n$ 为偶数），其中 $l$ 只左袜子，$r$ 只右袜子。每只袜子有颜色 $c_i$ （$1 \le c_i \le n$） 。 现在你有三个操作，每个操作代价为 $1$： 1.将某只袜子颜色换为 $c'$，（$1 \le c' \le n$） 2.将左袜子变为右袜子 3.将右袜子变为左袜子 求使所有袜子匹配成 $\frac n2$ 对袜子（即，颜色相同，且左右袜子各一）的代价。 ### 输入格式 第一行一个数 $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$），为 $n$ 只袜子的颜色。其中，前 $l$ 个数为左袜子，后 $r$ 个数为右袜子。