解释
猜测:对于选哪个点比较好直观上应该建在中间,因为如果建在靠近两端的话都会因为另一端距离货舱距离过大而导致总距离过大。基于此,可以推测总距离与位置关系为一个U型。
做法;(排序后)可以先把最初的点建在中间距离算一下总距离,然后分别向两边枚举如果比之小或等于则继续枚举,否则直接break。之所以比之大就break是因为最低点不管向左还是向右都是递增的,所以再往后枚举就递增了,所以必须break;
算法1
时间复杂度
O(n*k): k与比较次数有关
参考文献
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6;
typedef long long ll;
int a[N],s[N];
int n;
ll minv;
ll find2(int w)//返回当货舱建在w时的总距离
{
ll sum=0;
for(int i=1;i<=n;i++) sum+=abs(a[i]-w);
return sum;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a,a+n+1);
minv=a[n]/2;//货舱首先建在中间点
int start;
for(int i=n;i>=1;i--) if(a[i]<=minv) {start=i;break;}//找一下离中间点最近的送货点,从这个送货点开始送
minv=find2(start);
for(int i=start+1;i<=n;i++)//向右枚举
{
if(find2(minv)>=find2(a[i]))
{
minv=a[i];
}
else break;
}
// cout<<start;
for(int i=start-1;i>=1;i--)//向左枚举
if(find2(minv)>=find2(a[i])) minv=(ll)a[i];
else break;
cout<<find2(minv);
return 0;
}