## 2013年3月22日

### UVa 12049 - Just Prune The List

```#include <cstdio>
#include <vector>
#include <algorithm>
using std::vector;
using std::sort;

const int H = 33331;

struct N {
N (int num, int cnt) : num(num), cnt(cnt) {}
int num, cnt;
};

void push(int n, vector<N>* v) {
int i, x = n % H;
for (i = 0; i < v[x].size(); i++)
if (v[x][i].num == n) {
v[x][i].cnt++;
return;
}
v[x].push_back(N(n, 1));
}

int find(int n, vector<N>* v) {
int i, x = n % H;
for (i = 0; i < v[x].size(); i++)
if (v[x][i].num == n) return v[x][i].cnt;
return 0;
}

int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
int i, n, m, a[10000], b[10000];
vector<N> h1[H], h2[H];
vector<int> all;
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++) {
scanf("%d", a + i);
push(a[i], h1);
all.push_back(a[i]);
}
for (i = 0; i < m; i++) {
scanf("%d", b + i);
push(b[i], h2);
all.push_back(b[i]);
}
sort(all.begin(), all.end());
int ans = 0;
for (i = 0; i < all.size(); i++) {
if (i && all[i] == all[i - 1]) continue;
int n1 = find(all[i], h1), n2 = find(all[i], h2);
ans += n1 > n2 ? n1 - n2 : n2 - n1;
}
printf("%d\n", ans);
}
return 0;
}
```