首页 > 代码库 > codeforces 489B. BerSU Ball 解题报告

codeforces 489B. BerSU Ball 解题报告

2024-08-03 00:57:17   220人阅读

题目链接：http://codeforces.com/problemset/problem/489/B

题目意思：给出 n 个 boys 的 skills 和 m 个 girls 的 skills，要求成 pair 的条件为，男和女的 skill 差值最多只能为 1。问成 pair 最多是多少。

    这个不太难，关键是要考虑周全。

　　对于某个人，假设他（男）的 skill 值为 i，那么跟他成 pair 的人的 skill 值，只有三种：i-1，i，i+1。跟他成对的女要减少一个。然后女的那边也要搜一遍，再输出较大的就是答案了。

    

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 100 + 5; 8 int a[maxn], b[maxn]; 9 10 int get_num(int ta[], int tb[])11 {12     int num = 0;13     for (int i = 1; i <= 100; i++)14     {15         if (ta[i])16         {17             for (int j = 0; j < ta[i]; j++)18             {19                 if (tb[i-1])20                 {21                     tb[i-1]--;22                     num++;23                 }24                 else if (tb[i])25                 {26                     tb[i]--;27                     num++;28                 }29                 else if (tb[i+1])30                 {31                     tb[i+1]--;32                     num++;33                 }34             }35         }36     }37     return num;38 }39 40 int main()41 {42     #ifndef ONLINE_JUDGE43         freopen("in.txt", "r", stdin);44     #endif45 46     int n, m, input;47     while (scanf("%d", &n) != EOF)48     {49         memset(a, 0, sizeof(a));50         memset(b, 0, sizeof(b));51 52         for (int i = 0; i < n; i++)53         {54             scanf("%d", &input);55             a[input]++;56         }57         scanf("%d", &m);58         for (int i = 0; i < m; i++)59         {60             scanf("%d", &input);61             b[input]++;62         }63         int ans = 0;64         ans = max(get_num(a, b), get_num(b, a));65         printf("%d\n", ans);66     }67     return 0;68 }

 

codeforces 489B. BerSU Ball 解题报告


联系
我们