题解：P14546 [IO 2024 #3] 整数中位数
xiao_qiu
·
·
题解
P14546 [IO 2024 #3] 整数中位数
题目描述
按照任意顺序逐个将数字添加到 $m$ 中，使得在每一步添加完当前数字后，集合 $m$ 元素的中位数始终保持为整数。
## 初始思路
我们假定一个情况，当数组处于一个稳定状态时，当且仅当在此之后我们以一种特定顺序添加 $a_i$ ，可以保证 $m$ 的中位数是整数。
是否可能有这个稳定状态存在呢？这时数组的奇偶性会给予我们很强的提示。
为什么是奇偶性？因为我们如果处于稳定状态，那么上述所说的特殊顺序更可能是以有序数列的中点为中心，左一个右一个地添加，这显然是成对出现的，也就是存在奇偶性区别。
至于为什么左右轮流添加可行，~~这就好比你在一层一层剥橘子一样，~~
这是在于我们只要先把两个中间的数加进来，之后成对加数不会改变 $m$ 的中位数。证毕。
## 具体着手
假设 $n$ 为偶数，那么根据刚刚的思路，我们将以左一个右一个的顺序添加 $a_i$ 。在进入稳定状态之前，我们一定要保证 $a_i$ 的中位数为整数。
这是显然的，当你把所有的 $a_i$ 加进去了，最终 $m$ 的中位数和原来 $a$ 数组的中位数就是一致的。后者不为整数，前者一定不为整数，条件就无法实现了。
而当 $a_i$ 的中位数为整数时，我们一定可以按照上述特殊顺序执行操作。请读者自证。
::::info[提示]
考虑加数的时候当前容量为奇数时发生什么？偶数时发生什么？
::::
假设 $n$ 为奇数，那我们考虑将未知问题转化为已知问题。接下来注意到一个重要推论：
```
如果我们移除一个数后，其余数满足偶数情况，那么奇数情况一定成立。
```
为什么？证明是显然的。
如果你移除一个数后，剩余的满足偶数条件，那你不妨先把除了这个数外的其他 $a_i$ 按照偶数情况加到 $m$ 里，最后再把这个数加进去。加完之后 $m$ 显然有奇数个整数，根据题意， $m$ 的中位数一定是整数，那么推论证毕。
## 代码实现
::::info[代码]
```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;
}
```
::::