算法1(绝对值不等式+分组)
时间复杂度$O(n)$
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n;
int a[101000];
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
int ans=0;
for(int i=0;i<n;i++)
{
ans+=abs(a[i]-a[n/2]);
}
cout<<ans<<endl;
return 0;
}
算法2(三分) O(n^logn)
位置从沿着数轴从左到右,答案从大到小到大,满足凹函数,可以用三分确定最小值
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int a[101000];
int check(int x)
{
int res=0;
for(int i=0;i<n;i++)
{
res+=abs(a[i]-x);
}
return res;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
int l=a[0],r=a[n-1];
while(l<r-1)
{
int midl=(l+r)>>1;
int midr=(midl+r)>>1;
if(check(midl)>check(midr))
l=midl+1;
else
r=midr;
}
cout<<min(check(l),check(r))<<endl;
return 0;
}