P7628 [COCI2011-2012#1] PLES

kkxacj · 2023-03-18 16:07:54 · 题解

题目传送门

引言：

考试时排序全写的加 n，导致洛谷上测只有 62 （这也能有 62），写个题解纪念一下。

思路

读题分析可知：

只有男孩 a 想和比他高的女孩 b 跳舞，女孩 b 想和比她矮的男孩 a 跳舞 或 女生 a 想和比她高的男孩 b 跳舞，男生 b 想和比他矮的女孩 a 跳舞，这样的两个人才会成为一对舞伴。

所以我们可以开四个数组，两个统计男生想和比他高的女孩跳舞和男孩想和比他矮的女孩跳舞的男生的身高，另外两个统计女孩想和比他高的男生跳舞和女孩想和比他矮的男孩跳舞的女生的身高，然后将四个数组排序，再比较即可。

注意：没有同样高的男孩和女孩想和对方跳舞。

code

#include<bits/stdc++.h>
using namespace std;
int n,x,o,oo,ooo,oooo,ans,a[1000010],b[1000010],c[1000010],d[1000010],l = 1;
bool cmp(int x,int y)
{
    return x > y;
}
int main()
{
//  freopen("dance.in","r",stdin);
//  freopen("dance.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) 
    {
        scanf("%d",&x);
        if(x < 0) a[++o] = x;
        else b[++oo] = x;
    }
    for(int i = 1;i <= n;i++) 
    {
        scanf("%d",&x);
        if(x < 0) c[++ooo] = x;
        else d[++oooo] = x;
    }
    sort(a + 1,a + 1 + o,cmp);//由于该数组统计的负数，绝对值小的反而大 ，所以应从大到小排 
    sort(c + 1,c + 1 + ooo,cmp);//同上 
    sort(b + 1,b + 1 + oo);
    sort(d + 1,d + 1 + oooo);
    for(int i = 1;i <= o;i++)
    {
        if(d[l] < -a[i] && l <= oooo)
        {
            ans++;
            l++;
        }
    }
    l = 1;
    for(int i = 1;i <= ooo;i++)
    {
        if(b[l] < -c[i] && l <= oo)
        {
            ans++;
            l++;
        }
    }
    printf("%d",ans);
    return 0;
}