P14546 整数中位数 题解

ARIS0_0 · 2025-11-20 14:50:00 · 题解

1. 题意解释

给出一个集合 S，将 S 中的所有数加入一个新的集合 S'，使得每次加入时 S' 的中位数为整数。

2. 思路

考虑排序数组，从中间开始一个个加入，这样就能保持处于中间的两个数相同。

当 n 为偶数时，显然取第 \dfrac{n}{2} 和 \dfrac{n}{2}+1 个数，若奇偶性不同则显然无解。

而当 n 为奇数时，有三个数，分别是第 \dfrac{n-1}{2}，\dfrac{n+1}{2}，\dfrac{n+3}{2} 个数，从中选取两个奇偶性相同的即可。

由鸽巢原理可知至少会有 2 个奇偶性相同的，因此可行。

3. 代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100100];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    if(n%2==0){
        if(a[n/2]%2!=a[n/2+1]%2){
            cout<<-1;
        }
        else{
            int l=n/2,r=n/2+1;
            for(int i=1;i<=n/2;i++){
                cout<<a[l]<<" "<<a[r]<<" ";
                l--,r++;
            }
        }
    }
    else{
        if(n==1){
            cout<<a[1];
        }
        else{
            int mid=(n+1)/2;
            if(a[mid]%2==a[mid-1]%2){
                cout<<a[mid-1]<<" "<<a[mid]<<" ";
                int l=mid-2,r=mid+2;
                for(int i=1;i<=n/2-1;i++){
                    cout<<a[l]<<" "<<a[r]<<" ";
                    l--,r++;
                }
                cout<<a[mid+1];
            }
            else if(a[mid]%2==a[mid+1]%2){
                cout<<a[mid]<<" "<<a[mid+1]<<" ";
                int l=mid-2,r=mid+2;
                for(int i=1;i<=n/2-1;i++){
                    cout<<a[l]<<" "<<a[r]<<" ";
                    l--,r++;
                }
                cout<<a[mid-1];
            }
            else if(a[mid-1]%2==a[mid+1]%2){
                cout<<a[mid-1]<<" "<<a[mid+1]<<" ";
                int l=mid-2,r=mid+2;
                for(int i=1;i<=n/2-1;i++){
                    cout<<a[l]<<" "<<a[r]<<" ";
                    l--,r++;
                }
                cout<<a[mid];
            }
        }
    }
    return 0;
}