题目链接

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

解题思路

`dif[i]`表示`l[i] - r[i]`，即同种颜色左脚袜子数减去右脚袜子数。答案为

代码

```#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;
}
```