当二分图去跑，匈牙利算法就好，注意记录某个点已经不能再改变其配对点，防止爆T
#include <iostream> #include <string> #include <cstdio> #include <algorithm> #include <vector> #include <stack> #include <queue> #define MAX 105 #define INF 0x3f3f3f3f using namespace std; int a[105], b[105], pre[205], used[205]; bool vis[105]; vector<int> G[105]; bool dfs(int v) { vis[v] = true; bool flag = false; for (int i = 0; i < G[v].size(); ++i) { int t = G[v][i]; if (used[t]) continue; int u = pre[t]; if (u) { if (!vis[u]) { bool f = dfs(u); if (f) { pre[t] = v; flag = f; break; } else { used[t] = true; } } } else { pre[t] = v; flag = true; break; } } vis[v] = false; return flag; } int main() { // freopen("a.txt", "r", stdin); // freopen("b.txt", "w", stdout); int n, m; cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; cin >> m; for (int i = 1; i <= m; ++i) cin >> b[i]; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (abs(a[i] - b[j]) <= 1) { G[i].push_back(j + 100); } } } int ans = 0; for (int i = 1; i <= n; ++i) { if (dfs(i)) { ans++; } } cout << ans << endl; return 0; }