如果某个士兵最后到达的位置已知,那么它具体怎么走是不会影响答案的.
为方便考虑,不妨让它们先走到同一个平行于x轴的直线y=k上.k取什么值时这一步的花费最小?其实就是”货仓选址”问题,将y坐标排序,取中位数即可.
那x轴上如何考虑?将x坐标排序.然后有一个性质:最优情况下,排序后士兵间的相对顺序和最后走到最终位置的相对顺序不会改变.
设最左边的士兵走到$x_1=a$处,那么由题意,第2个走到$x_2=a+1$处,第i个走到$x_i=a+i-1$处.
那么,第i个士兵要走$|x_i-(a+i-1)|=|x_i-(i-1)-a|$单位距离.
将$x_i-(i-1)$看成一个整体,问题就又转化为”货仓选址”问题了,对$x_i-(i-1)$排序,取中位数即可.
时间复杂度$O(nlogn)$
//Wan Hong 3.0
//notebook
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
typedef unsigned un;
typedef std::string str;
typedef long long ll;
typedef std::pair<ll,ll> pll;
ll read()
{
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
bool umin(ll &a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
bool umax(ll &a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
ll abs(ll x)
{
return x>0?x:-x;
}
/**********/
#define MAXN 200011
ll x[MAXN],y[MAXN];
int main()
{
ll n=read(),ans=0;
for(ll i=1;i<=n;++i)x[i]=read(),y[i]=read();
std::sort(x+1,x+n+1);
std::sort(y+1,y+n+1);
ll mid_y=y[(n+1)>>1];
for(ll i=1;i<=n;++i)
ans+=abs(y[i]-mid_y);
for(ll i=1;i<=n;++i)
{
x[i]-=(i-1);
}
std::sort(x+1,x+n+1);
ll mid_x=x[(n+1)>>1];
for(ll i=1;i<=n;++i)
ans+=abs(x[i]-mid_x);
printf("%lld",ans);
return 0;
}
妙
看了那么多终于有一个能看懂的了
太妙了
“排序后士兵间的相对顺序和最后走到最终位置的相对顺序不会改变.”这个性质总结的好啊