当前位置: 代码迷 >> 综合 >> 51Nod 1096 - 距离之和最小
  详细解决方案

51Nod 1096 - 距离之和最小

热度:57   发布时间:2023-12-24 11:18:56.0

题目大意:中文题

解题思路:把所有数排序以后,找中位数,既是所需要找到点。注意要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;
}