【每日一题】Problem 489B. BerSU Ball

原题

解决思路

排序+双指针

#include <bits/stdc++.h>

int main() {
  int n; std::cin >> n;
  std::vector<int> a(n + 1, 0);
  for (int i = 1; i <= n; ++i) std::cin >> a[i];

  int m; std::cin >> m;
  std::vector<int> b(m + 1, 0);
  for (int i = 1; i <= m; ++i) std::cin >> b[i];

  std::sort(a.begin(), a.end());
  std::sort(b.begin(), b.end());

  int pa, pb; pa = pb = 1;
  int ans = 0;
  while (pa < a.size() && pb < b.size()) {
    if (std::abs(a[pa] - b[pb]) <= 1) {
      ++pa;
      ++pb;
      ++ans;
    } else if (a[pa] > b[pb]) {
      ++pb;
    } else {
      ++pa;
    }
  }
  std::cout << ans << std::endl;
}

误区

是否存在 \(a[i]\) 与 \(a[i-1]\) 同时可以配对 \(b[j]\) 的情况，而由于 \(a[i]\) 提前与 \(b[j]\) 配对，导致后续 \(a[n]\) 无法与 \(b[m]\) 配对以及影响之后的配对情况？
答：不存在，最多是 \(a[i]\) 与 \(a[n]\) 一换一，总数量不变，不影响 \(a[n+1]\) 及之后的情况，可以用递推和反证法证明