题目大意:中文题
解题思路:把所有数排序以后,找中位数,既是所需要找到点。注意要long long 保存结果证明如下:
我们可以想象现在x轴上有n个点,我们设定的目标点在最左边,那么可以算出距离总和ans。
目标点往右移动1,相当于ans+左边点数-右边点数。
那么目标点到达正中央(或中央两点之间)前,ans单调递减(左边点<右边点),之后ans又单调递增(左 边点>右边点)
由此,目标点为中位数点时,距离之和最小。(来自:http://www.bubuko.com/infodetail-1915008.html)
ac代码:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{int n, a[10005];long long sum;while (scanf("%d", &n)!=EOF){sum = 0;for (int i=0; i<n; i++)scanf("%d", &a[i]);sort(a, a+n);for (int i=0; i<n; i++)sum += abs(a[i] - a[n/2]);printf("%lld\n", sum);}
return 0;
}