有n个男孩和m个女孩(1≤n,m≤100),我们知道他们每个人的技能值(男孩为a[i],女孩为b[i],每个技能值都≤100)。
当且仅当第A个男孩和第B个女孩的技能值相差不超过1时,他们将成为一对舞伴。
给定n、m和他们各自的技能值,输出他们能组成的舞伴最大对数(格式见样例)。
思路:贪心。先分别排序,设定两个指针,然后进行是否配对判断,直到其中一个指针指到最后为止。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn], b[maxn], n, m;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
for (int i = 1; i <= m; i++) cin >> b[i];
sort (a + 1, a + n + 1);
sort (b + 1, b + m + 1);
int p1 = 1, p2 = 1;
int ans = 0;
while (p1 <= n && p2 <= m) {
if (abs(a[p1] - b[p2]) <= 1) p1++, p2++, ans++; //如果可以配对
else if (a[p1] > b[p2])p2++; //如果a[i] > b[j] j++
else if (a[p1] < b[p2])p1++; //如果a[i] < b[j] i++
}
cout << ans << endl;
return 0;
}