idea
中位数就是最优解
相关题目
- 一维扩展到二维(三分),模拟退火(高维)
写法1 $(nlogn)$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false),cin.tie(0);
ll n;
cin >> n;
ll a[n];
for (ll i = 0 ; i < n; ++ i) cin >> a[i];
sort(a, a + n);
ll ans = 0;
for (ll i = 0; i < n ; ++ i) ans += abs(a[n / 2] - a[i]); // 也可以用a[i] - a[i / 2],这是等价的。
cout << ans << endl;
return 0;
}
优化写法 $(n)$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false),cin.tie(0);
ll n;
cin >> n;
ll a[n];
for (ll i = 0 ; i < n; ++ i) cin >> a[i];
nth_element(a, a + n / 2, a + n);
ll ans = 0;
for (ll i = 0; i < n ; ++ i) ans += abs(a[n / 2] - a[i]); // 也可以用a[i] - a[i / 2],这是等价的。
cout << ans << endl;
return 0;
}