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.