#P4989. 小英雄的火腿促销
小英雄的火腿促销
Description
众所周知XLX开了一个火腿小店,这天店里还剩下 n只火腿,其中有 L只左腿和 R 只右腿LX决定搞个促销活动,买一只羊左腿配一只羊右腿可以打折!这样就可以让火腿卖的快点一点,早点卖完早点收工
但是顾客总是挑剔的,他们在选择左腿和右腿时,必须要保证这两只腿出自同一品种的羊,否则他们会不高兴购买
LX自然是知道自己这 n 只火腿分别出自哪个品种的羊——第 i 只火腿出自 a_i 编号品种的羊
但是LX的技术手段总是那么的高超,他可以通过一次手术让某只火腿发生变化,可以发生的变化有三种:
1. 让编号为 i 的火腿品种变成 x
2. 让编号为 i 的火腿从左腿变成右腿
3. 让编号为 i 的火腿从右腿变成左腿
一次手术只能让一只火腿发生其中一种变化(可以对一只火腿进行多次手术)
现在LX想知道,至少需要多少次手术,可以让他现有的 n 只火腿成功配上对?
P.S. 这里的配对是指,同一品种的一只左腿和一只右腿配对
Input Format
输入第一行包含三个正整数 n,L,R 分别表示羊腿总数和左腿右腿的数量
输入第二行包含 n 个整数 ai,分别表示每一只羊腿的品种编号,其中前 L 只羊腿是左腿,后 R 只是右腿
数据保证 n=L+R
数据范围
对于 30% 的数据保证: 2≤n≤10
对于 60% 的数据保证: 2≤n≤2000
对于 100% 的数据保证: 2≤n≤200000
对于所有数据保证:n 是偶数,1≤L,R,ai≤n , L+R=n
Output Format
输出一个整数,表示XLX最少需要进行几次手术样例解释1
其中一组方案为:
第一次手术将3号火腿从右腿变成左腿
第二次手术将1号火腿品种变为2
第三次手术将2号火腿品种变为2
</span>
6 2 4
1 1 2 2 2 23