（C++）ZOJ-4096——Thanks, TuSimple!（贪心算法）

古城微笑少年丶 2021-12-01 11:16 196阅读 0赞

### 题目描述 ###

作为TuSimple的经理，您将为开发部门和营销部门举办舞会。 总共会有 n 个绅士和 m 个女士，他们会成对跳舞。 经过仔细调查后，我们已经知道，对于每个人来说，他们喜欢与较高的人或身高较小的人跳舞。 为了简化问题，没有两个身高相同的人，只允许人与异性的人跳舞。 为了保留适当的舞蹈场地，您必须计算同时跳舞的最大可能人数。

### 题目解析 ###

这道题可以用贪心的思想来解决，而且跳舞的人的喜好一定是0和1配对的

*  首先男性和女性中的0和1分开，所以对男性和女性根据喜好从小到大排序
 *  而对于相同喜好的人则根据身高从低到高排序
 *  我们让0和1去配对，即我们希望尽量每次可以进行配对，那么我们让喜好为0的人，去和喜好为1且身高最低的异性去匹配

### 源代码（可AC） ###

#include<iostream>
    #include<algorithm>
    using namespace std;
    const int maxn=2e5+7;
    struct People
    {
        
        int h;
        int like;
    }man[maxn],lady[maxn];
    bool cmp(People& a,People& b)
    {
        
        if(a.like==b.like)
            return a.h<b.h;
        return a.like<b.like;
    }
    int main()
    {
        
        int t;
        cin>>t;
        while(t--)
        {
        
            int n,m,ans=0;
            int M0=0,L0=0;
            cin>>n>>m;
            for(int i=0;i<n;++i)
                cin>>man[i].h;
            for(int i=0;i<m;++i)
                cin>>lady[i].h;
            for(int i=0;i<n;++i)
            {
        
                cin>>man[i].like;
                if(man[i].like==0)
                    ++M0;
            }
            for(int i=0;i<m;++i)
            {
        
                cin>>lady[i].like;
                if(lady[i].like==0)
                    ++L0;
            }
            sort(man,man+n,cmp);
            sort(lady,lady+m,cmp);
    
            int j=L0;
            for(int i=0;i<M0&&j<m;++i)
            {
        
                if(man[i].h>lady[j].h)
                {
        
                    ++ans;
                    ++j;
                }
            }
            j=M0;
            for(int i=0;i<L0&&j<n;++i)
            {
        
                if(lady[i].h>man[j].h)
                {
        
                    ++ans;
                    ++j;
                }
            }
    
            /*int x=0;
            for(int i=0;i<M0;++i)
            {
                //cout<<'*'<<endl;
                int flag=0;
                for(int j=L0+x;j<m;++j)
                {
                    if(man[i].h>lady[j].h)
                    {
                        ++ans;
                        ++flag;
                        break;
                    }
    
                }
                if(flag!=0)
                {
                    ++x;
                }
    
            }
            x=0;
            for(int i=0;i<L0;++i)
            {
                //cout<<'*'<<endl;
                int flag=0;
                for(int j=M0+x;j<n;++j)
                {
                    if(man[j].h<lady[i].h)
                    {
                        ++ans;
                        ++flag;
                        break;
                    }
                }
                if(flag!=0)
                {
                    ++x;
                }
                //cout<<x<<endl;
    
            }*/
            cout<<ans<<endl;
        }
    }