题目链接

https://codeforces.com/problemset/problem/1515/D

解题思路

第一步：先将左右脚袜子个数经转换变成一样的；
第二步：变色。
也就是说先变类型至左右脚相等，再变色得到完全匹配。

先说第二步，假设经过一定的算法后左右脚袜子个数相等了。
设dif[i]表示l[i] - r[i]，即同种颜色左脚袜子数减去右脚袜子数。答案为

如何将袜子数变换成一致的：
假设初始右袜子个数大于左袜子个数，则若dif[i] <= -2，则将此颜色的一根右袜子变成左袜子；待全部颜色的袜子都按此方式循环完后，仍无法使左右袜子数一致，则再次循环。若dif[i] == -1，则将此颜色的一根右袜子变成左袜子，直至左右袜子数相等。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;

int T, n, l, r;
int ll[N], rr[N], dif[N];

int main()
{
    cin>>T;
    while(T--) {
        cin>>n>>l>>r;
        int ans = max(l-r, r-l)/2;
        int maxcol = 0;
        int col;
        memset(ll, 0, sizeof ll);
        memset(rr, 0, sizeof rr);

        for(int i = 0;i < l;i ++) cin>>col, ll[col] ++, maxcol = max(col, maxcol);
        for(int i = 0;i < r;i ++) cin>>col, rr[col] ++, maxcol = max(col, maxcol);
        for(int i = 0;i <= maxcol;i ++) dif[i] = ll[i] - rr[i];
        if(l < r) {
            for(int i = 0;i <= maxcol;i ++) {
                while(l < r) {
                    if(dif[i] <= -2) dif[i] +=2, l++, r--;
                    else break;
                }
            }
            if(l < r) {
                for(int i = 0;i <= maxcol;i ++) {
                    if(dif[i] == -1) dif[i] = 1, l++, r--;
                    if(l == r) break;
                }
            }
        } else if(l > r) {
            for(int i = 0;i <= maxcol;i ++) {
                while(r < l) {
                    if(dif[i] >= 2) dif[i] -=2, r++, l--;
                    else break;
                }
            }
            if(l < r) {
                for(int i = 0;i <= maxcol;i ++) {
                    if(dif[i] == 1) dif[i] = -1, r++, l--;
                    if(l == r) break;
                }
            }
        }

        int sum = 0;    
        for(int i = 0;i <= maxcol;i ++) sum += abs(dif[i]);
        ans += sum/2;

        cout << ans << endl;
    }
    return 0;
}