题解：P3439 [POI2006] MAG-Warehouse

· · 题解

来点无脑做法。

首先把切比雪夫距离转化成曼哈顿距离。

具体来说，对于点 (x_1,y_1) 与 (x_2,y_2) 的切比雪夫距离等于点 (\frac{x_1+y_1}{2},\frac{x_1-y_1}{2}) 与 (\frac{x_2+y_2}{2},\frac{x_2-y_2}{2}) 的曼哈顿距离。

那么现在可以把所有点 (x_i,y_i) 换成 (x_i+y_i,x_i-y_i)，问题就变成了找一个点，使得曼哈顿距离最小，注意我这里是没有除以二的，最后要除回去才对。

变成曼哈短距离最大的好处就是把横纵坐标的 \max 换成了加法，这使得我们可以横纵坐标分别考虑。

先做答案的横坐标 x，那么纵坐标问题是对称的，我们现在只考虑横坐标咋做，我们要最小化：

\sum\limits_{i=1}^n|x_i-x|k_i

直接把 k_i 看做是有 k_i 个 x_i，那么就是数轴上有若干个点，我们要求一个点使得到所有点的距离之和最小，根据初中数学老师告诉我们的结论，直接取中间的那个点即可，证明还是很简单的，可以考虑若干个绝对值函数加起来，最小值必然在斜率为 0 的点上，那么这个点必然是中点。

于是就做完了。

但是还有一个问题，最后复原答案的时候有一步要除一个 2，这样可能会使得和真实的答案相差 O(1) 个位置，直接暴力判断周围距离不超过 2 的点中最优的那一个即可。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
struct node{
    int x,k;
}a[100005],b[100005];
int x[100005],y[100005],k[100005];
signed main(){
    cin>>n;
    __int128 s=0;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i]>>k[i];
        s+=k[i];
        a[i].x=x[i]+y[i];
        b[i].x=x[i]-y[i];
        a[i].k=b[i].k=k[i];
    }
    sort(a+1,a+1+n,[](node x,node y){
        return x.x<y.x;
    });
    sort(b+1,b+1+n,[](node x,node y){
        return x.x<y.x;
    });
    int pos1=0,pos2=0,t=0;
    for(int i=n;i;i--){
        t+=a[i].k;
        if(t*2>=s){
            pos1=a[i].x;
            break;
        }
    }
    t=0;
    for(int i=n;i;i--){
        t+=b[i].k;
        if(t*2>=s){
            pos2=b[i].x;
            break;
        }
    }
    int X=pos1+pos2;
    int Y=pos1-pos2;
    X>>=1,Y>>=1;
    __int128 minn=1e30;
    int ansx=0,ansy=0;
    for(int i=-2;i<=2;i++){
        for(int j=-2;j<=2;j++){
            if(X+i<1||X+i>5e8||Y+j<1||Y+j>5e8) continue;
            s=0;
            for(int p=1;p<=n;p++){
                s+=max(abs(X+i-x[p]),abs(Y+j-y[p]))*k[p];
            }
            if(s<minn){
                minn=s;
                ansx=X+i;
                ansy=Y+j;
            }
        }
    }
    cout<<ansx<<' '<<ansy<<'\n'; 
}