P14546 整数中位数题解

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. 代码实现

CPP

#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;
}

P14546 整数中位数题解

文章操作

1. 题意解释

2. 思路

3. 代码实现

相关推荐

评论

P14546 整数中位数题解