题解 P3439 【[POI2006]MAG-Warehouse】

oscar

2017-10-03 23:12:03

Solution

【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; } ```