[TIOJ 1293] I.送貨倉庫

作法：

這題用到的技巧之前有遇過類似的，例如 HOJ 86 - 接金幣，和 IOI 2007 - pairs ( HOJ 256 )，都是用到類似的座標變換手法。

如果定義的距離是曼哈頓距離的話( | x1-x2 | + | y1-y2 | )，就可以對 x , y 分開做了，並且他會等價於中位數的問題。所以大概會考慮一個座標變換，讓兩個點變換前的距離( 這個指題目定義的 ) 會等於兩個點變換後的曼哈頓距離，那麼就好做了。而這只要考慮 ( x , y ) -> ( x + y , x - y ) ，不難驗證他會滿足上面那件事。

但實際上還要多考慮一些東西，因為這樣會發現變換後的所有點 ( x , y ) 都會滿足 x , y 同為奇數或偶數，所以如果求出的答案坐標相加是奇數的話就會沒辦法對應回原坐標的點，所以在新座標平面上的最好的點不一定可行，答案可能會是次好的點。而我的解決方法是先把在新座標平面上的可能的點們找出來( 至多4個 )，如果他們坐標和是奇數，那就考慮他的上下左右四個點，加入候選人，但這樣沒辦法知道到底哪一個比較好，所以我直接再對每個候選人 O( n ) 算一次他的值，並更新答案。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100000+10 ;
 
struct P
{
    int pos,val ;
    bool operator < (const P &rhs) const
    {
        return pos==rhs.pos ? val<rhs.val : pos<rhs.pos ;
    }
};
 
P x[maxn],y[maxn] ;
bool found ;
int n,ansx,ansy ;
LL ans ;
 
void solve(vector<int> &v,P *p)
{
    LL sum=0LL ;
    for(int i=1;i<=n;i++) sum+=p[i].val ;
    LL now=0LL ;
    for(int i=1;i<=n;i++)
    {
        now+=p[i].val ;
        if(sum%2 && 2*now>sum) { v.push_back(p[i].pos) ; break ; }
        else if(sum%2==0)
        {
            if(2*now==sum)
            {
                v.push_back(p[i].pos) ;
                v.push_back(p[i+1].pos) ;
                break ;
            }
            else if(2*now>sum)
            {
                v.push_back(p[i].pos) ;
                break ;
            }
        }
    }
}
 
LL cal(int x0,int y0)
{
    LL ret=0LL ;
    for(int i=1;i<=n;i++)
        ret+= ((LL)x[i].val)*
            (x0>=x[i].pos ? (LL)x0-x[i].pos : (LL)x[i].pos-x0 ) ,
        ret+= ((LL)y[i].val)*
            (y0>=y[i].pos ? (LL)y0-y[i].pos : (LL)y[i].pos-y0 ) ;
    return ret ;
}
 
bool better(int x0,int y0)
{
    if(!found) return 1 ;
    LL tmp=cal(x0,y0) ;
    if(tmp!=ans) return tmp<ans ;
 
    if(2*ansx!=x0+y0) return x0+y0<2*ansx ;
    if(2*ansy!=x0-y0) return x0-y0<2*ansy ;
    return 0 ;
}
 
void update(int x0,int y0)
{
    if(better(x0,y0))
        ansx=(x0+y0)/2 , ansy=(x0-y0)/2 ,
        ans=cal(x0,y0) , found=1 ;
}
 
main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            int a,b,t ; scanf("%d%d%d",&a,&b,&t) ;
            x[i]=(P){a+b,t} ; y[i]=(P){a-b,t} ;
        }
        sort(x+1,x+n+1) ;
        sort(y+1,y+n+1) ;
 
        found=0 ;
        vector<int> vx,vy ;
        solve(vx,x) ; solve(vy,y) ;
        for(auto i : vx) for(auto j : vy)
        {
            if((i+j)%2==0) update(i,j) ;
            else
            {
                update(i,j-1) , update(i,j+1) ;
                update(i-1,j) , update(i+1,j) ;
            }
        }
        printf("%d %d\n",ansx,ansy) ;
    }
}