CodeForces 489B (贪心 或 最大匹配) BerSU Ball

时间：2021-08-30 20:47:09

题意：

有m个男孩和n个女孩，每个人都有一个舞蹈熟练度，用一个不超过100的正整数来表示。

一个男孩和一个女孩能够结为舞伴当且仅当两人的熟练度相差不超过1.

问最多能结成多少对舞伴

分析：

这是一个二分图最大匹配问题，如果男孩和女孩满足条件则添加一条边，然后用匈牙利算法求最大匹配即可。

这是匈牙利算法的模板

http://www.cnblogs.com/AOQNRMGYXLMV/p/3950653.html

题解中还给了一种贪心的解法。将两边的熟练度排序，然后匹配。

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int a[maxn], b[maxn], line[maxn][maxn], used[maxn], girl[maxn];

 int n, m;

 int main()

 {

     int cnt = ;

     scanf("%d", &n);

     for(int i = ; i < n; ++i)  scanf("%d", &a[i]);

     scanf("%d", &m);

     for(int i = ; i < m; ++i)  scanf("%d", &b[i]);

     sort(a, a + n);

     sort(b, b + m);

     for(int i = ; i < n; ++i)

         for(int j = ; j < m; ++j)

         {

             if(abs(a[i] - b[j]) <= )

             {

                 cnt++;

                 b[j] = ;        //标记这个妹子有舞伴了

                 break;

             }

         }

     printf("%d\n", cnt);

     return ;

 }

代码君

相关文章