自动搬运

查看原文

来自洛谷，原作者为

	kkxacj Full of Hope.

搬运于2025-08-24 22:31:41，当前版本为作者最后更新于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;
}