本文共 1074 字，大约阅读时间需要 3 分钟。

题目来源：

Description

学校周末举办舞会，有 n 位男同学和 m 位女同学参加。每位同学的舞蹈熟练度可能不一样，要求男同学与女同学之间搭配形成搭档，且舞蹈熟练度最多相差 1。

分别给出每位男同学的舞蹈熟练度与每位女同学的舞蹈熟练度，需要能求出可以组合的最多的搭档数量。

Input

第一行仅有一个整数 n (1 ≤ n ≤ 100)，表示男同学的数量。

第二行有一个整数序列，a1, a2, …, an (1 ≤ ai ≤ 100)，ai 表示每个男同学的舞蹈熟练度。 第三行仅有一个整数 m (1 ≤ m ≤ 100)，表示女同学的数量。 第四行有一个整数序列，b1, b2, …, bm (1 ≤ bi ≤ 100)，bi 表示每个男同学的舞蹈熟练度。

Output

输出一个整数，表示能组合出搭档的最多数量。

Sample Input

4

1 4 6 2 5 5 1 5 7 9

Sample Output

3

解题思路

这次要我们做的是给男生女生分配舞伴，问题是要求出最多舞蹈者组数，也就是求一个最优答案，所以往后的目标就在于：如何做到每一步“看起来最优”

也就是让每一个舞者所配对的人都恰好处在条件（升高差 < 1 ）边缘

那么我们可以先将男女生身高分别排序。

然后贪心的找就行了。

AC代码：

#include 
   
    using namespace std;#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define endl '\n'const int MAXN = 105;int a[MAXN],b[MAXN];int main(){
       SIS;    int n,m;    cin >> n;    for(int i=0;i
    
     > a[i];    cin >> m;    for(int i=0;i
     
      > b[i];    sort(a,a+n);    sort(b,b+m);    int i=0,j=0,ans=0;    while(i
      
       1) j++;        else if(b[j]-a[i]>1) i++;        else ans++,i++,j++;    }    cout << ans << endl;    return 0;}
      
     
    
   

转载地址：http://vsyof.baihongyu.com/