思路:中位数即为最优
时间复杂度:$O(nlogn)$
- 从两个点的最优情况为
a - b
再拓展到多个点即可! - 可以将式子表示出来,进行前后(最后一个和最前一个)两两组合,会发现要想最优即要满足每组的两点之间,即为中位数。
特别的:下面的写法也是对的!可通过数学式子展开来证明!
res += a[i] - a[i / 2];
具体证明过程可以参考视频或抽风大佬题解!
参考代码:
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
int main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
int res = 0;
for(int i = 0; i < n; i++) res += abs(a[i] - a[n / 2]);
cout << res << endl;
return 0;
}