题解 | 买一送一-牛客假日团队赛2A题

题目描述

Farmer John在网上买干草。他发现了一笔特殊的买卖。他每买一捆大小为的干草，他就能免费获得一捆大小为的干草！
然而，这笔交易是有规定的：大的一捆干草必须是高质量的，小的一捆是低质量的。FJ是个吝啬鬼，他并不在意：随便什么质量，只要能省钱就好。
给出一组捆高质量干草的大小，捆低质量的干草的大小，找出Farmer John最多能买多少捆干草。他能买高质量的干草而不拿免费的低质量干草，但他不能买低质量的干草（就是说，他只能通过增送来获得）。

第 1 行: 两个用空格分开的整数，和

第 2 至 行: 第行包含一个整数，是第i捆高质量干草的大小。

第 至 行: 第行包含一个整数，是第捆低质量干草的大小。

第 1 行: Farmer John能买的最大的干草的捆数。

示例1

3 4
6
1
3
1
5
3
4

5

有3捆高质量干草，大小是6，1，3，4捆低质量的干草，大小是1，5，3，4
显然，Farmer John能买所有的高质量的干草。当他买了大小为6的高质量干草，他可以免费拿任何一捆低质量干草（例如大小为3的）。当他买了大小为3的高质量干草，他可以拿大小为1的免费低质量干草。然而当他买了大小为1的高质量干草，就不能拿不了免费干草了（因为大小必须严格小于）。这样，无论FJ有多聪明，最多也只能拿5捆干草了。

解答

#include<bits/stdc++.h>
 
using namespace std;
const int maxn = 2e5 + 10;
    int a[maxn],b[maxn];
int main()
{
    int n,m;
    cin>>n>>m;
 
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<m;i++)
        cin>>b[i];
    sort(b,b+m);
    int cnt = 0;
    for (int i = 0;i < n;i++)
    {
        if (cnt < m && b[cnt]<a[i])
            cnt++;
    }
    cout << n+cnt << endl;
 
    return 0;
}