UVA 10057 中位数

本文主要是介绍UVA 10057 中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给出N个数，求出其中一个数A，所有数与这个数的差的绝对值之和最小。

这个数必须是中位数。

假设N是奇数，对于中位数MID，左边有N/2个数，右边有N/2个数。假设此时和为SUM。

如果A不选择MID，而是选择MID左边一个数的话，则左边的数到A的距离均减一，右边的数加上中位数到MID距离加一。SUM‘=SUM+1，SUM增大，同理右边。

所以必须是中位数。

对于带权中位数。对于每一个权值不为1的点，可以先按位置排个序，对于权值不为一的点，拆成N个位置相同权值为1的点，在这个新的数列中求中位数，等价于求

第（权值总和/2）个数。

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;int num[1000003];
int n;
int getSum(int a)
{return upper_bound(num+1,num+n+1,a)-lower_bound(num+1,num+n+1,a);
}
int main()
{//freopen("acm.in","r",stdin);while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++)scanf("%d",&num[i]);sort(num+1,num+1+n);int m=(1+n)>>1;if(n%2)printf("%d %d %d\n",num[m],getSum(num[m]),1);else{int sum=0;if(num[m+1]!=num[m])sum=getSum(num[m])+getSum(num[m+1]);elsesum=getSum(num[m]);printf("%d %d %d\n",num[m],sum,num[m+1]-num[m]+1);}}return 0;
}

这篇关于UVA 10057 中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---