题目描述

难度分:$1200$

输入$n(1 \leq n \leq 100)$和长为$n$的数组$a(1 \leq a[i] \leq 100)$。

输入$m(1 \leq m \leq 100)$和长为$m$的数组$b(1 \leq b[i] \leq 100)$。

你可以从$a$、$b$中各选一个数字，组成一个数对$(a[i],b[j])$，要求$|a[i]-b[j]| \leq 1$。

选过的数字不能再选，最多可以选出多少个数对？

输入样例$1$

4
1 4 6 2
5
5 1 5 7 9

输出样例$1$

3

输入样例$2$

4
1 2 3 4
4
10 11 12 13

输出样例$2$

0

输入样例$3$

5
1 1 1 1 1
3
1 2 3

输出样例$3$

2

算法

匈牙利算法

这个题很容易就能看出来是二分图的最大匹配模型，把数组$a$中的元素用$[1,n]$编号，$b$中的元素用$[1+n,m+n]$编号。如果$|a[i]-b[j]| \leq 1$，说明$i$和$j$之间有边连接。

1. 按照这个逻辑，双重循环建无向图。

2. 接下来在这个无向图上跑匈牙利算法做二分图的最大匹配即可。

复杂度分析

时间复杂度

匈牙利算法的时间复杂度为$O(ne)$，其中$n$为$a$中的元素数量，相当于图中“左边”顶点$a$的数量，它们要去匹配“右边”顶点$b$的数量。而$e$是图中边的数量，在本题中最差情况下是个稠密图，边的数量是$nm$。因此，整个算法的时间复杂度为$O(n^2m)$。

空间复杂度

空间消耗的瓶颈在于图的邻接表、标记数组$st$和匹配数组$match$。它们的空间是同一级别，均为$O(n+m)$，这也是整个算法的额外空间复杂度。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 110;
int n, m, a[N], b[N], match[N<<1];
vector<int> graph[N<<1];
bool st[N<<1];

bool find(int u) {
    for(int v: graph[u]) {
        if(!st[v]) {
            st[v] = true;
            if(match[v] == 0 || find(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d", &b[i]);
    }
    for(int i = 1; i <= n + m; i++) {
        graph[i].clear();
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(abs(a[i] - b[j]) <= 1) {
                graph[i].push_back(j + n);
                graph[j + n].push_back(i);
            }
        }
    }
    memset(match, 0, sizeof(match));
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        memset(st, 0, sizeof st);
        if(find(i)) ans++;
    }
    printf("%d\n", ans);
    return 0;
}