题解 P4612 【[COCI2011-2012#7] SETNJA】

· · 题解

P4612

这题AC率挺高的说，窝wa了一次，为组织蒙羞（所用人交19，AC15）

那么Solution:

I存储

可以观察到，Mirko的朋友可以接到Mirko的范围是一个矩形,如：

那么以便方便我们就用结构体来存

struct node 
{
    int ux,dx,ly,ry;
}a[400100];
------------ ### $II$转移范围 我们可以发现，$Mirko$的出发点一定是在第一个朋友可以接到的范围内（不一定是在边缘上，即$t = a[1]

可以记t为Mirko可以待的范围，从曾经范围内的点走相同的最短步数d而得来，如图

假设红色的范围是曾经可以待的范围（因为有时候保证最优的不止一个点），

那么每次更新出一个新的范围

而这个范围一定是个矩形，那么之后就说矩形吧（记几yy一下

III如何转移矩形

可以观察出，从当前所在的矩形t要转移到a[i](i >= 2)

共有两种可能：

然后把t更新为交集 交集求法 ``` node Get_(node a1,node a2) { node b = (node){min(a1.ux,a2.ux),max(a1.dx,a2.dx),max(a1.ly,a2.ly),min(a1.ry,a2.ry)}; if(b.ux < b.dx || b.ly > b.ry)return (node){-1,-1,-1,-1}; return b; } ``` 如果无交集，就更新为$-1$，以便于接下来判断 $2$、$t$ 与 $a[i]$ 无交集，那么需要走 ```d = max(max(a[i].dx-t.ux,t.dx-a[i].ux),max(a[i].ly-t.ry,t.ly-a[i].ry));``` $a$.内部第一个$max$：一个矩形$a$的下底减去另一个矩形$b$的上底（反着再来一次 （解释一下内部$max$：我们要求的是距离最近的$a$与$b$的边的距离 即，竖着走的最小步数（没错，就是最小，自己借助下图$yy $c$.外部$max$：因为在斜着走的时候可以分成走两步，譬如，左上 = 左走$1$+上走$1

那么横竖两方向走的少的就可以被抵消，最小步数就是大的那个

呃，不好理解呢，画个图吧

最后

t = Get_((node){t.ux+d,t.dx-d,t.ly-d,t.ry+d},a[i]);ans += (long long )d;
--- $ACcode 
#include <cstdio>
#include <algorithm>
using namespace std;
int N,x,y,p;
struct node 
{
    int ux,dx,ly,ry;
}a[400100]; 
node Get_(node a1,node a2)
{
    node b = (node){min(a1.ux,a2.ux),max(a1.dx,a2.dx),max(a1.ly,a2.ly),min(a1.ry,a2.ry)};
    if(b.ux < b.dx || b.ly > b.ry)return (node){-1,-1,-1,-1};
    return b;
}
int main()
{
    scanf("%d",&N);
    for(int i = 1 ; i <= N ; i ++ )
    {
        scanf("%d%d%d",&x,&y,&p);
        a[i] = (node){x + p,x - p,y - p,y + p};
    }
    node t = a[1];long long ans = 0;
    for(int i = 2 ; i <= N ; i ++ )
    {
        node b = Get_(a[i],t);
        if(b.dx != - 1){t = b;continue;}
        int d = max(max(a[i].dx-t.ux,t.dx-a[i].ux),max(a[i].ly-t.ry,t.ly-a[i].ry));
        t = Get_((node){t.ux+d,t.dx-d,t.ly-d,t.ry+d},a[i]);ans += (long long )d;
    }
    printf("%lld",ans);
    return 0;
}

其实还可以在化简下

首先结构体变量有两个即可（节能主义万岁！!!

每次更新下 l 经过计算可以发现 在求交集时，如果相交，那么 ``` d = max(max(now.dx-l.ux,l.dx-now.ux),max(now.ly-l.ry,l.ly-now.ry)) ``` 一定$<0

那么我们使d = 0 ,反正原来如果有交集，ans也什么都不加

最后更新下t

#include <cstdio>
#include <algorithm>
using namespace std;
int N,x,y,p;
struct node 
{
    int ux,dx,ly,ry;
}l,now; 
int main()
{
    scanf("%d",&N);scanf("%d%d%d",&x,&y,&p);
    l = (node){x + p,x - p,y - p,y + p};
    long long ans = 0;
    for(int i = 2 ; i <= N ; i ++ )
    {
        scanf("%d%d%d",&x,&y,&p);
        now = (node){x + p,x - p,y - p,y + p};
        int d = max(max(now.dx-l.ux,l.dx-now.ux),max(now.ly-l.ry,l.ly-now.ry));
        if(d < 0)d = 0;
        ans += (long long)d;
        l.dx = max(l.dx - d,now.dx);
        l.ux = min(l.ux + d,now.ux);
        l.ly = max(l.ly - d,now.ly);
        l.ry = min(l.ry + d,now.ry);
    }
    printf("%lld",ans);
    return 0;
}