题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5979

题意

前面都是废话，题目从图片下面的第一段话开始！

n个男生，m个女生，给出男生的身高ai，女生的身高bi,任何两个人的身高都不相同。

如果p=0表示ta想要和比ta身高矮的人配对，p=1表示ta想要和比ta身高高的人配对。

求异性之间成功配对的对数。

 

解题思路

两个人之间内能配对一定要满足，x想要高的，y想要矮的，且y比x高。

对男生身高排序，p不同时p=0的排在前面，相同时身高按升序排，读入的时候记录p=0的个数cnt0。

对女生身高排序，p不同时p=1的排在前面，相同时身高按升序排，读入的时候记录p=1的个数cnt1。

接下来模拟匹配过程就ok了。注意：一定是两个p不同的异性之间比较身高！

时间复杂度O(nlogn) 

 

ac代码

男女身高分别排序

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define  maxn 100005
typedef long long ll;
using namespace std;
struct node{
    ll height;
    ll want;
}a[maxn],b[maxn];//a 男生，b 女生
bool cmpa(node a,node b)//男生先排0
{
    return a. want==b.want?a.height<b.height:a.want<b.want;
}
bool cmpb(node a,node b)//女生先排1
{
    return a.want==b.want?a.height<b.height:a.want>b.want;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll n,m,cnt1=0,cnt0=0,ans=0;//a-cnt0,b-cnt1
        //读入
        scanf("%lld %lld",&n,&m);
        for(ll i=0;i<n;i++)
            scanf("%lld",&a[i].height);
        for(ll i=0;i<m;i++)
            scanf("%lld",&b[i].height);
        for(ll i=0;i<n;i++)
        {
            scanf("%lld",&a[i].want);
            if(!a[i].want) cnt0++;
        }
        for(ll i=0;i<m;i++)
        {
            scanf("%lld",&b[i].want);
            if(b[i].want) cnt1++;
        }
        //排序
        sort(a,a+n,cmpa);
        sort(b,b+m,cmpb);
        //匹配
        for(ll i=0,j=0;i<cnt0 && j<cnt1; )//i-a0,j-b1,男高女矮
        {
            if(a[i].height>b[j].height)
            {
                ans++;
                i++;j++;
            }
            else i++;//男的不够高，往下找高的
        }
        for(ll i=cnt0,j=cnt1;i<n && j<m; )//男矮女高
        {
            if(a[i].height<b[j].height)
            {
                ans++;
                i++;j++;
            }
            else j++;//女的不够高
        }
        printf("%lld\n",ans);
    }
    return 0;
}

男女身高同样的排序方法，男女分别记录p=0的个数（from:https://blog.csdn.net/sdau_fangshifeng/article/details/89300201）

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define PI acos(-1.0)
#define pppp cout<<endl;
#define EPS 1e-8
#define LL long long
#define ULL unsigned long long     //1844674407370955161
#define INT_INF 0x3f3f3f3f      //1061109567
#define LL_INF 0x3f3f3f3f3f3f3f3f //4557430888798830399
// ios::sync_with_stdio(false);
// 那么cin, 就不能跟C的 scanf，sscanf, getchar, fgets之类的一起使用了。
const int dr[]= {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[]= {-1, 1, 0, 0, -1, 1, -1, 1};
int read()//输入外挂
{
    int ret=0, flag=0;
    char ch;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        ret = ch - '0';
    while((ch=getchar())>='0'&&ch<='9')
        ret=ret*10+(ch-'0');
    return flag ? -ret : ret;
}
const int maxn=100050;
struct node
{
    int heigh;
    int select;
} a[maxn],b[maxn];
bool cmp(node x,node y) //排序，现把0放在前面，1放在后面
{
    if(x.select==y.select)
        return x.heigh<y.heigh;
    else
        return x.select<y.select;
}
int main()
{
    freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m); //全部初始化为未匹配点
        for(int i=0; i<n; ++i)
            scanf("%d",&a[i].heigh);
        for(int i=0; i<m; ++i)
            scanf("%d",&b[i].heigh);

        int cnt1=0;//男生0的个数
        int cnt2=0;//女生0的个数
        for(int i=0; i<n; ++i)
        {
            scanf("%d",&a[i].select);
            if(!a[i].select)
                ++cnt1;
        }
        for(int i=0; i<m; ++i)
        {
            scanf("%d",&b[i].select);
            if(!b[i].select)
                ++cnt2;
        }

        sort(a,a+n,cmp);
        sort(b,b+m,cmp);


        int num=0;
        int j=cnt2;
        for(int i=0; i<cnt1; ++i) //男生高，女生矮
        {
            if(a[i].heigh>b[j].heigh)
            {
                num++;
                j++;
            }
            if(j>=m)
                break;
        }

        j=cnt1;
        for(int i=0; i<cnt2; ++i) //女生高，男生矮
        {
            if(b[i].heigh>a[j].heigh)
            {
                num++;
                j++;
            }
            if(j>=n)
                break;
        }
        printf("%d\n",num);
    }
    return 0;
}