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

沒有留言:

張貼留言