具有最小绝对差之和的数组元素？
在这里，我们将看到一个有趣的问题。我们采用一个包含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
热门推荐
10 圣诞祝福语简短小学
11 祖国七十华诞简短祝福语
12 老师送的祝福语简短
13 生日祝福语大全女生简短
14 祝女性生日祝福语简短
15 牛年女神节祝福语简短
16 情人表白祝福语简短大气
17 老公开业祝福语简短
18 官宣新年祝福语简短