speike

众所周知，Speike 狗是一条特别喜欢追着Tom 打的狗。

现在，Tom 又把Speike 惹生气了，现在Speike 需要跨越千山万水找Tom 报仇。

Speike 所在的世界可以看成是一个无穷大的平面，平面由一个平面直角坐标系确定。在平面上有许多不相交的矩形障碍，矩形的四边平行于坐标轴。

Speike 需要从 $(X_t,0)(Xt,0)，也就是Tom 在的位置。$

出题人规定，Speike 只能沿着平行于坐标轴的方向运动，且不能进入矩形障碍的内部，但是可以在障碍边界上移动。

所有障碍的横坐标都在 $[0,X_t][0,Xt] 之内。保证矩形不相交(即没有公共面积)，也不会退化成线段或者点。$

Speike 的智商不是很高，因此他需要你帮忙设计一条最短的路线。当然，你只需要告诉他路线的长度就行了。

第一行一个整数

第二行一个整数 $X_tXt，代表终点的横坐标。$

第三行开始，共

共一行，一个整数，代表最短路线的长度。

共下发三个样例，分别与第2; 4; 11 号测试点的数据范围与特性一致。

测试点编号	n的范围	特殊性质
1		无
2,3		无
4,5,6		$X_{t} inleft[-10^{3}, 10^{3} ight]a,b,c,d,Xt∈[−103,103]$
7,8,9,10		$X_{t} inleft[-10^{5}, 10^{5} ight]a,b,c,d,Xt∈[−105,105]$
11,12,13		$X_{t} inleft[-10^{3}, 10^{3} ight]a,b,c,d,Xt∈[−103,103]$
14,15		无
16,17	$10^5n≤105$	所有矩形都与
18,19,20	$10^5n≤5×105$

$-10^{8} leq a, c leq X_{t} leq 10^{8},-10^{8} leq b, d leq 10^{8}, n inleft[0,10^{5} ight]−108≤a,c≤Xt≤108,−108≤b,d≤108,n∈[0,105]。保证矩形不相交(即没有公共面积)，每个矩形不会退化成线段或者点，且横坐标都在 [0,X_t][0,Xt] 之内。$

CSP-S 2019模拟长沙一中2

Solution

我就把题解的话复读一边：

考虑一条路线，x一定是单调增的。

而且该路线一定贴着矩形的边。

那么我们可以把矩形按左边的线排序，对于每一个矩形考虑他的左边两个端点,找到最近一个可以转移的矩形转移就行。

找矩形可以线段树或者set

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 1000006
#define lb(x) lower_bound(Y+1,Y+m+1,x)-Y
#define mid ((l+r)>>1)
#define ls k<<1
#define rs k<<1|1
using namespace std;
int n,ed,Y[maxn],f[maxn][2],t;
int tr[maxn*4];
struct node{
    int a,b,c,d;
}s[maxn];
bool cmp(node A,node B){
    return A.a<B.a;
}
void add(int k,int l,int r,int li,int ri,int v){
    if(l>=li&&r<=ri){tr[k]=v;return;}
    if(li<=mid)add(ls,l,mid,li,ri,v);
    if(ri>mid)add(rs,mid+1,r,li,ri,v);
}
void ask(int k,int l,int r,int pl){
    t=max(t,tr[k]);
    if(l==r)return;
    if(pl<=mid)return ask(ls,l,mid,pl);
    return ask(rs,mid+1,r,pl);
}
int main(){
    cin>>n>>ed;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d%d",&s[i].a,&s[i].b,&s[i].c,&s[i].d);
        if(s[i].a>s[i].c)swap(s[i].a,s[i].c);
        if(s[i].b>s[i].d)swap(s[i].b,s[i].d);
        Y[i]=s[i].d,Y[i+n]=s[i].b;
    }
    
    int N=n+n+1;Y[N]=0;
    sort(Y+1,Y+N+1);int m=unique(Y+1,Y+N+1)-Y-1;
    s[++n]=(node){ed,0,ed,0};
    sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++){
        t=0;ask(1,1,m,lb(s[i].b));
        f[i][0]=min(f[t][0]+abs(s[t].b-s[i].b),f[t][1]+abs(s[t].d-s[i].b));
        t=0;ask(1,1,m,lb(s[i].d));
        f[i][1]=min(f[t][0]+abs(s[t].b-s[i].d),f[t][1]+abs(s[t].d-s[i].d));
        add(1,1,m,lb(s[i].b),lb(s[i].d),i);
    }
    cout<<f[n][0]+ed<<endl;
    return 0;
}

View Code

speike

speike

题目描述

输入格式

输出格式

样例

数据范围与提示

来源