题解：P2874 [USACO07FEB] Building A New Barn G

根据曼哈顿距离的定义，

ans=\sum |Dx-x_i|+\sum |Dy-y_i|

，其中

(Dx,Dy)

是曼哈顿距离最小的点。

根据小学奥数可以知道，对于一个一维的序列，若要让

\sum |x-a_i|

最小，那么

x

就一定是序列

a

的中位数。

这一点也可以扩展到二维上，然后就做完了。

但是这道题不能取输入数据中的点，直接对答案微调一下即可。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int> 
#define fi first 
#define se second 
const int N=1e5+5;

int n,ax[N],ay[N];
pii a[N];
bool cmp(pii x,pii y){
    return x.se<y.se;
}

const int dir[4][2]={1,0,0,1,0,-1,-1,0};
const int INF=INT_MAX;

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].fi>>a[i].se,ax[i]=a[i].fi,ay[i]=a[i].se;
    sort(ax+1,ax+n+1); sort(ay+1,ay+n+1);

    if(n%2){
        int cnt=0,dis=INF;
        int sx=ax[(n+1)/2],sy=ay[(n+1)/2];
        for(int i=0;i<4;i++){
            int nx=sx+dir[i][0],ny=sy+dir[i][1];
            int tmp=0;
            for(int j=1;j<=n;j++) tmp+=abs(a[j].fi-nx)+abs(a[j].se-ny);
            if(tmp<dis) dis=tmp,cnt=1;
            else if(tmp==dis) cnt++;
        }
        return cout<<dis<<" "<<cnt<<"\n",void();
    }
    else{
        int cnt=0,dis=0;
        int sx1=ax[n/2],sx2=ax[n/2+1];
        int sy1=ay[n/2],sy2=ay[n/2+1];
        cnt=(sx2-sx1+1)*(sy2-sy1+1);
        for(int i=1;i<=n;i++) dis+=abs(a[i].fi-sx1)+abs(a[i].se-sy1);
        for(int i=1;i<=n;i++) if((a[i].fi==sx1||a[i].fi==sx2)&&(a[i].se==sy1||a[i].se==sy2)) cnt--;
        return cout<<dis<<" "<<cnt<<"\n",void();
    }

}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T=1;
    while(T--){
        solve();
    }

    return 0;
}

题解：P2874 [USACO07FEB] Building A New Barn G

文章操作

相关推荐

评论

题解：P2874 [USACO07FEB] Building A New Barn G