P14546 [IO 2024 #3] 整数中位数

题目描述

n

个互不相同的整数，第

i

个数为

a_i

。按照任意顺序逐个将数字添加到

m

中，使得在每一步添加完当前数字后，集合

m

元素的中位数始终保持为整数。

初始思路

我们假定一个情况，当数组处于一个稳定状态时，当且仅当在此之后我们以一种特定顺序添加

a_i

，可以保证

m

的中位数是整数。

是否可能有这个稳定状态存在呢？这时数组的奇偶性会给予我们很强的提示。

为什么是奇偶性？因为我们如果处于稳定状态，那么上述所说的特殊顺序更可能是以有序数列的中点为中心，左一个右一个地添加，这显然是成对出现的，也就是存在奇偶性区别。

至于为什么左右轮流添加可行，~~这就好比你在一层一层剥橘子一样，~~

这是在于我们只要先把两个中间的数加进来，之后成对加数不会改变

m

的中位数。证毕。

具体着手

假设

n

为偶数，那么根据刚刚的思路，我们将以左一个右一个的顺序添加

a_i

。在进入稳定状态之前，我们一定要保证

a_i

的中位数为整数。

这是显然的，当你把所有的

a_i

加进去了，最终

m

的中位数和原来

a

数组的中位数就是一致的。后者不为整数，前者一定不为整数，条件就无法实现了。

而当

a_i

的中位数为整数时，我们一定可以按照上述特殊顺序执行操作。请读者自证。

提示

考虑加数的时候当前容量为奇数时发生什么？偶数时发生什么？

假设

n

为奇数，那我们考虑将未知问题转化为已知问题。接下来注意到一个重要推论：

CPP

如果我们移除一个数后，其余数满足偶数情况，那么奇数情况一定成立。

为什么？证明是显然的。

如果你移除一个数后，剩余的满足偶数条件，那你不妨先把除了这个数外的其他

a_i

按照偶数情况加到

m

里，最后再把这个数加进去。加完之后

m

显然有奇数个整数，根据题意，

m

的中位数一定是整数，那么推论证毕。

代码实现

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],ret,b[N];
void p_work()
{
	for(int i=(n>>1);i;i--) printf("%d %d ",a[i],a[n-i+1]);
	return;
}
bool check()
{
	for(int i=1;i<=n;i++) 
	{
		int l=i-1,r=n-i;
		int posl,posr,mid=(n-1)>>1;
		if(l==r) posl=i-1,posr=i+1;
		else if(mid+1<=l) posl=mid,posr=mid+1;
		else posl=mid+1,posr=mid+2;
//		printf("i=%d posl=%d,posr=%d\n",i,posl,posr);
		if((a[posl]+a[posr])%2==0)
		{
			ret=a[i];
			for(int j=1;j<=i-1;j++)  b[j]=a[j];
			for(int j=i+1;j<=n;j++) b[j-1]=a[j];
			return true;
		}
	}
	return false;
}
void q_work()
{
	for(int i=((n-1)>>1);i;i--) printf("%d %d ",b[i],b[n-i]);
	printf("%d",ret);
	return;
}
signed main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	if(n%2==0)  
	{
//		printf("pos:%d %d\n",n>>1,(n>>1)+1);
		if((a[n>>1]+a[(n>>1)+1])%2==0) p_work();
		else puts("-1");
	}
	else
	{
		if(!check()) puts("-1");
		else q_work();
	}
	return 0;
}

题解：P14546 [IO 2024 #3] 整数中位数

文章操作