题意

题目链接。

有 $n$ 只袜子，每只袜子都可能是左/右袜子且有一种颜色。每次操作你可以：改变袜子的颜色或改变袜子的左右性。你需要使左右袜子一一配对（具体地，若两只袜子一左一右且颜色相同，则这两只袜子配对）。求最小操作数。

解析

首先由于左右袜子必须要一一配对，所以两者数量一定要相等，因此答案最小为 $|\frac{l-r}{2}|$，即我们至少要进行 $|\frac{l-r}{2}|$ 次更改左右性的操作。我们考虑怎么使这些操作收益最大化，即操作后改变颜色的操作数最小。

穿插一个小证明：我们一定只会进行 $|\frac{l-r}{2}|$ 次更改左右性的操作。因为假设左右袜子数相等，我们最优再进行两次更改左右性操作才能使两对袜子配对，而更改颜色也只需要两次，没必要再进行更改左右性的操作。

首先我们可以先把已经配好对的袜子排除掉，显然改变已配对的袜子的左右性是愚蠢的。又有显然地，更改左右性的操作只会在袜子多的那边进行。假设左袜子多，那么对于左袜子中未匹配的袜子，如果有一种颜色的袜子不少于两只，更改其中一只的左右性一定是更优的，因为这样更改之后就直接匹配了，无需再更改颜色。先尽可能找出这种袜子，然后剩下的袜子就随意了，最后统计答案时再加上仍未得到匹配的袜子数即可。

代码附有注释，可食用。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int T,n,l,r,ans,x;
int c[N],tl[N],tr[N];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&l,&r);
        ans=abs(l-r)/2;//更改左右性的操作数
        for(int i=1;i<=n;i++) tl[i]=tr[i]=0;
        for(int i=1;i<=n;i++) scanf("%d",&c[i]);
        for(int i=1;i<=l;i++) tl[c[i]]++;
        for(int i=l+1;i<=n;i++) tr[c[i]]++;
        for(int i=1;i<=n;i++){
            if(tl[i]>0&&tr[i]>0){
                int t=min(tl[i],tr[i]);
                tl[i]-=t;
                tr[i]-=t;//这里是去除已配对的袜子
            }
        }
        int x=ans;
        if(l>r){//找袜子多的那边，进行操作
            for(int i=1;i<=n&&x>0;i++){
                while(x>0&&tl[i]>=2){//如果有不少于 2 只的，选它
                    x--;
                    tl[i]-=2;//一只左右性换了，一只匹配上了，故未匹配的直接减 2
                }
            }
            for(int i=1;i<=n&&x>0;i++){
                while(x>0&&tl[i]>=1){//处理剩余的操作次数
                    x--;
                    tl[i]-=1;//未匹配的袜子数只能减 1
                }
            }
            for(int i=1;i<=n;i++){
                ans+=tl[i];//答案加上未匹配的袜子数
            }
        }
        else{//同上
            for(int i=1;i<=n&&x>0;i++){
                while(x>0&&tr[i]>=2){
                    x--;
                    tr[i]-=2;
                }
            }
            for(int i=1;i<=n&&x>0;i++){
                while(x>0&&tr[i]>=1){
                    x--;
                    tr[i]-=1;
                }
            }
            for(int i=1;i<=n;i++){
                ans+=tr[i];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}