题意
题目链接。
有 $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;
}