#include<cstdlib> #include<iostream> #include<cstdio> #include<cmath> #include<set> #include<cstring> #include <algorithm> #define N 1000000 #define MIN 1e-11 #define M 32010 #define MM 70000 using namespace std; int n,t; int a[N]; int cmp(const void *a,const void *b) { return *(int*)a-*(int*)b; } int main() { #ifndef ONLINE_JUDGE freopen("ex.in","r",stdin); #endif while(scanf("%d",&n)!=EOF) { for(int i=0;i<n;++i) scanf("%d",&a[i]); qsort(a,n,sizeof(a[0]),cmp); int mid=(n-1)/2; printf("%d ",a[mid]); int cnt=0; if(n&1) { for(int i=mid;i<n;i++) if(a[i]==a[mid]) cnt++; else break; for(int i=mid-1;i>=0;i--) if(a[i]==a[mid]) cnt++; else break; printf("%d 1\n",cnt); } else { for(int i=mid;i<n;i++) if(a[i]==a[mid]) cnt++; else break; if(a[mid+1]!=a[mid]) cnt++; for(int i=mid-1;i>=0;i--) if(a[i]==a[mid]) cnt++; else break; printf("%d ",cnt); if(a[mid+1]!=a[mid]) printf("%d\n",a[mid+1]-a[mid]+1); else printf("1\n"); } } return 0; }
分析与总结:
求出A,使得(|X1-A| + |X2-A| + … … + |Xn-A|)的值最小。
那么这个A其实就是中位数。那么在排序之后,
如果数字个数为奇数,那么中间那个就是唯一的中位数,如果是偶数,则会有中间的两位数,而且在这两位数之间的数也是。
再求数列中有几个数时需要注意的是,奇数是求出中间两个数之后,这两个数的旁边也可能会有相等的数