</p><p>在这里,我们将看到一个有趣的问题。我们有一个包含N个元素的数组'a'。我们需要找到一个元素x,使得|a[0] - x| + |a[1] - x| + ... + |a[n-1] - x|的值最小化。然后我们需要找到最小化的和。</p><p>假设数组为:{1, 3, 9, 6, 3},现在x为3。所以和为|1 - 3| + |3 - 3| + |9 - 3| + |6 - 3| + |3 - 3| = 11。</p><p>为了解决这个问题,我们需要选择数组的中位数作为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