题解 P3439 【[POI2006]MAG-Warehouse】

2017-10-03 23:12:03


【POI补全计划#23 POI2006 MAG】

终于有道(我会做的)没人做的题了

这题的思路很妙,嘿嘿

一开始看到“切比雪夫距离”我也是一脸懵○,心想着如果是曼哈顿距离我就会做了

嗯...先来讲讲曼哈顿距离的情况怎么做

我们发现曼哈顿距离对于x方向和y方向是独立的,于是转换成一维情况

一维情况就很好解决了(类似中位数,调整法可证)

--------------------分割线----------------------------

那么切比雪夫距离怎么做呢?

我们来把到一个点切比雪夫距离为k的所有点画出来,发现是一个正着放的正方形

再把所有到一个点曼哈顿距离为k的所有点画出来,发现是一个转了45度的正方形

emmmmmmm...

这样就好办了,只需要把坐标系转45度,求新坐标系下的曼哈顿距离版本问题就好了

什么?你问我怎么转45度?

只需要将坐标轴改为x+y和x-y即可(最后不要忘了转回来)

最后有一点细节需要注意

求出来的答案可能不是整点,需要额外验证一下附近的点(x坐标±1,y坐标±1(开区间),共1或4个整点)

(写个SPJ还得用__int128 ......)

贴代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100010;
struct pt
{
    int x,y,cnt;
}a[MAXN],b[MAXN],c[MAXN];
int n;
inline bool cmpx(const pt &a,const pt &b)
{
    return a.x<b.x;
}
inline bool cmpy(const pt &a,const pt &b)
{
    return a.y<b.y;
}
inline long long check(int x,int y)
{
    unsigned long long ret=0;
    for(int i=1;i<=n;i++)
    {
        ret+=max(abs(x-c[i].x),abs(y-c[i].y))*(long long)c[i].cnt;
    }
    return ret;
}
int main()
{
    int u,v,w;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        a[i].x=u+v,a[i].y=u-v,a[i].cnt=w;
        b[i].x=u+v,b[i].y=u-v,b[i].cnt=w;
        c[i].x=u,c[i].y=v,c[i].cnt=w;
    }
    sort(a+1,a+n+1,cmpx);
    sort(b+1,b+n+1,cmpy);
    int posx,posy;
    int l=1,r=n;//d:l-r
    while(l<r)
    {
        if(a[l].cnt<a[r].cnt)
        {
            a[r].cnt-=a[l].cnt;
            l++;
        }
        else if(a[l].cnt>a[r].cnt)
        {
            a[l].cnt-=a[r].cnt;
            r--;
        }
        else
        {
            l++;
            r--;
        }
    }
    posx=a[l].x;
    l=1,r=n;
    while(l<r)
    {
        if(b[l].cnt<b[r].cnt)
        {
            b[r].cnt-=b[l].cnt;
            l++;
        }
        else if(b[l].cnt>b[r].cnt)
        {
            b[l].cnt-=b[r].cnt;
            r--;
        }
        else
        {
            l++;
            r--;
        }
    }
    posy=b[l].y;
    int xx=(posx+posy)/2,yy=(posx-posy)/2;
    unsigned long long sum1=check(xx,yy),
                       sum2=check(xx+1,yy),
                       sum3=check(xx,yy+1),
                       sum4=check(xx+1,yy+1),
                       minn=0xffffffffffffffffllu;
    int mins=0;
    if(sum1<minn)mins=1,minn=sum1;
    if(sum2<minn)mins=2,minn=sum2;
    if(sum3<minn)mins=3,minn=sum3;
    if(sum4<minn)mins=4,minn=sum4;
    if(mins==1)printf("%d %d\n",xx,yy);
    if(mins==2)printf("%d %d\n",xx+1,yy);
    if(mins==3)printf("%d %d\n",xx,yy+1);
    if(mins==4)printf("%d %d\n",xx+1,yy+1);
    return 0;
}