在这里，我们将看到一个有趣的问题。我们有一个包含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
#include
#include
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
