题解 P3439 【[POI2006]MAG-Warehouse】
oscar
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 ......)
贴代码:
```cpp
#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;
}
```