具有最小绝对差之和的数组元素？
在这里，我们将看到一个有趣的问题。我们采用一个包含N个元素的数组'a'。我们必须找到一个元素x使得|a[0]-x|+|a[1]-x|+…+|a[n-1]-x|被最小化。然后，我们必须找到最小化的总和。
令数组为：{1，3，9，6，3}现在x为3。所以总和为|1-3|。+|3-3|+|9-3|+|6-3|+|3-3|=11。
为了解决这个问题，我们必须选择数组的中位数为x。如果数组大小为偶数，则将有两个中值。它们都是x的最佳选择。
算法
minSum(arr,n)
begin
sort array arr
sum := 0
med := median of arr
for each element e in arr, do
sum := sum + |e - med|
done
return sum
end示例
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int minSum(int arr[], int n){
sort(arr, arr + n);
int sum = 0;
int med = arr[n/2];
for(int i = 0; i<n; i++){
sum += abs(arr[i] - med);
}
return sum;
}
int main() {
int arr[5] = {1, 3, 9, 6, 3};
int n = 5;
cout << "Sum : " << minSum(arr, n);
}输出结果
Sum : 11