中位数
中位数
http://www.nowcoder.com/questionTerminal/47232470945644458213ddd07580e121
题解:
考察点: 思维,数形结合
解法:
题目中要求的是让成为新数列的中位数,则说明把新数列按照从小到大顺序排序后,
要正好处于
的位置,于是采用数形结合的思想来解决此问题最为简单。首先统计原数组中小于
的元素个数
,大于
的元素个数
,等于
的元素个数
。于是会出现有下图
种情况:
如左边所示,若的元素个数多于
,为了要使得
位于中间位置,应该使得
变得一样长,则增加的元素应该为
。如右图所示,若
的元素多于
,由于
的位置是取不超过
的整数,于是
的长度至少要变得比
大1,否则中位数位置一定位于
半区,所以增加元素应该为
。最后,如果
和
一样长,那如果不存在
则要增加
个元素,否则
自动位于中位数的位置上,复杂度
#include "bits/stdc++.h" using namespace std; const int maxn=1e5+100; int n,m,a[maxn]; int main() { scanf("%d%d",&n,&m); int small=0,big=0,equal=0; for(int i=0;i<n;i++){ scanf("%d",&a[i]); if(a[i]<m) small++; else if(a[i]>m) big++; else equal++; } if(small<big) printf("%d\n",max(big-small-equal,0)); else if(small>big) printf("%d\n",max(small-big-equal+1,0)); else{ if(equal==0) printf("1\n"); else printf("0\n"); } return 0; }