LuoguP3964 [TJOI2013]松鼠聚会【切比雪夫距离/前缀和】

题目传送门

前置知识：切比雪夫距离和曼哈顿距离的相互转化--自为风月马前卒

有了这个知识，我们便可以在读入松鼠的家的坐标时，先把他转化一下，然后把最后的总式化简，我们会得到一个充满后缀和以及前缀和的式子，这里有十分详细的展开式。于是我们把$x$,$y$坐标分别排序并求出他们的前缀和即可。

之后我们枚举每个点，在这个点意义下求出答案，更新答案最小值。

Code

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 int n;

 ll tmp,ans=1e16;

 ll subx[],suby[];

 ll rx[],ry[];

 struct node{

     ll x,y;

 }p[];

 ll check(int u)

 {

     int pos=;

     ll ax=,ay=;

     pos=lower_bound(rx+,rx++n,p[u].x)-rx;

     ax+=pos*p[u].x-subx[pos];

     ax+=subx[n]-subx[pos]-p[u].x*(n-pos);

     pos=lower_bound(ry+,ry++n,p[u].y)-ry;

     ay+=pos*p[u].y-suby[pos];

     ay+=suby[n]-suby[pos]-p[u].y*(n-pos);

     return ax+ay;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         ll x=,y=;

         scanf("%lld%lld",&x,&y);

         rx[i]=x+y;ry[i]=x-y;

         p[i].x=rx[i],p[i].y=ry[i];

     }

     sort(rx+,rx++n);

     sort(ry+,ry++n);

     for(int i=;i<=n;i++)

         subx[i]=subx[i-]+rx[i],suby[i]=suby[i-]+ry[i];

     for(int i=;i<=n;i++)

         tmp=check(i),ans=min(ans,tmp);

     printf("%lld",ans>>);

     return ;

 }

* 注意观察式子，在前缀和那里不要用错=w=...

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 int n;

 ll tmp,ans=1e16;

 ll subx[],suby[];

 ll rx[],ry[];

 struct node{

     ll x,y;

 }p[];

 ll check(int u)

 {

     int pos=;

     ll ax=,ay=;

     pos=lower_bound(rx+,rx++n,p[u].x)-rx;

     ax+=pos*p[u].x-subx[pos];

     ax+=subx[n]-subx[pos-]-p[u].x*(n-pos);

     pos=lower_bound(ry+,ry++n,p[u].y)-ry;

     ay+=pos*p[u].y-suby[pos];

     ay+=suby[n]-suby[pos-]-p[u].y*(n-pos);

     return ax+ay;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         ll x=,y=;

         scanf("%lld%lld",&x,&y);

         rx[i]=x+y;ry[i]=x-y;

         p[i].x=rx[i],p[i].y=ry[i];

     }

     sort(rx+,rx++n);

     sort(ry+,ry++n);

     for(int i=;i<=n;i++)

         subx[i]=subx[i-]+rx[i],suby[i]=suby[i-]+ry[i];

     for(int i=;i<=n;i++)

         tmp=check(i),ans=min(ans,tmp);

     printf("%lld",ans>>);

     return ;

 }

WA