牛客网 提高组第8周 T2 推箱子 解题报告

时间：2023-01-23 21:24:50

推箱子

链接：

https://ac.nowcoder.com/acm/contest/176/B

来源：牛客网

题目描述

在平面上有\(n\)个箱子，每个箱子都可以看成一个矩形，两条边都和坐标轴平行。任何两个矩形都不相交，但可能有某个点或某条边重合。约定\(x\)轴正方向为右，\(y\)轴正方向为上。

现在\(\tt{Fizzydavid}\)要推这些箱子。他会选择某个箱子开始，并以每秒\(1\)个单位的速度使这个箱子向右移动。如果路上正面碰上某个箱子，被碰上的箱子会在碰到的那个瞬间开始进入运动状态，以\(1\)个单位的速度向右移动，不会转动或改变运动方向。

准确地说，在某个时刻一个箱子\(i\)处于移动状态当且仅当：\(i\)是选择的箱子，或者存在一个处于移动状态的箱子\(j\)，它的右边界等于箱子\(i\)的左边界，且它们在\(y\)轴上的投影的公共长度\(>0\)。你可以发现在这种情况下，任意时刻每个矩形仍然不相交。

\(\tt{Fizzydavid}\)告诉了你所有的信息，需要你求出\(k\)秒后每个矩形的位置。

输入描述:

第一行两个整数\(n\),\(t\)和\(k\)。\(\tt{Fizzydavid}\)开始选择的是输入的第\(t\)个矩形。

接下来\(n\)行每行四个整数\(x_{1,i},y_{1,i},x_{2,i},y_{2,i}\)，表示矩形的左下角坐标是\((x_{1,i},y_{1,i})\)，右上角坐标是\((x_{2,i},y_{2,i})\)。

输出描述:

输出一行\(n\)个整数，第\(i\)个整数表示\(k秒\)后第\(i\)个矩形的左下角的\(x\)坐标。你可以发现只要知道这个值就能唯一确定矩形的位置。

说明

对于\(30\%\)的数据，\(k\le 100\)。

对于另外\(40\%\)的数据，\(n\le 1000\)。

对于所有的数据，\(n\le 10^5\)，\(1\le t\le n\)，\(1\le k\le 10^9\)，所有坐标都在\(-10^9\)和\(10^9\)之间。保证任意两个矩形不相交。

据说正解是优化连边最短路算法？为什么不试试类似扫描线的算法呢？（考场上线段树数组开小爆\(70\)了

按照矩形的左边界\(x\)坐标为关键字进行排序，从最开始的那个矩形一个一个做过去。

具体的，对矩形在\(y\)轴方向的凸起用线段树维护，每次加入一个矩形的时候查询\(y\)上面区间的最大值，然后看能不能顶到\(\tt{Ta}\)

支持区间赋值和区间最大值就可以了，离散化和动态开点都可以。注意覆盖情况的小细节。

Code:

#include <cstdio>

#include <cstring>

#include <algorithm>

const int N=2e5+10;

struct node

{

    int s,t,l,r,id;

    bool friend operator <(node n1,node n2){return n1.s<n2.s;}

}mat[N];

int y[N<<1],cnt,n,t,k;

int tag[N<<2],mx[N<<2],ans[N],Time[N];

#define ls id<<1

#define rs id<<1|1

int max(int x,int y){return x>y?x:y;}

void pushdown(int id)

{

    if(~tag[id])

    {

        mx[ls]=mx[rs]=tag[ls]=tag[rs]=tag[id];

        tag[id]=-1;

    }

}

void change(int id,int L,int R,int l,int r,int d)

{

    if(l==L&&r==R)

    {

        mx[id]=max(mx[id],d);

        tag[id]=mx[id];

        return;

    }

    pushdown(id);

    int Mid=L+R>>1;

    if(r<=Mid) change(ls,L,Mid,l,r,d);

    else if(l>Mid) change(rs,Mid+1,R,l,r,d);

    else change(ls,L,Mid,l,Mid,d),change(rs,Mid+1,R,Mid+1,r,d);

    mx[id]=max(mx[ls],mx[rs]);

}

int query(int id,int L,int R,int l,int r)

{

    if(l==L&&r==R) return mx[id];

    pushdown(id);

    int Mid=L+R>>1;

    if(r<=Mid) return query(ls,L,Mid,l,r);

    else if(l>Mid) return query(rs,Mid+1,R,l,r);

    else return max(query(ls,L,Mid,l,Mid),query(rs,Mid+1,R,Mid+1,r));

}

int main()

{

    memset(tag,-1,sizeof(tag));

    memset(mx,-1,sizeof(mx));

    scanf("%d%d%d",&n,&t,&k);

    for(int i=1;i<=n;i++)

    {

        scanf("%d%d%d%d",&mat[i].s,&mat[i].l,&mat[i].t,&mat[i].r);

        --mat[i].r;

        y[++cnt]=mat[i].r,y[++cnt]=mat[i].l,mat[i].id=i;

    }

    std::sort(y+1,y+1+cnt);

    cnt=std::unique(y+1,y+1+cnt)-y-1;

    for(int i=1;i<=n;i++)

    {

        mat[i].l=std::lower_bound(y+1,y+1+cnt,mat[i].l)-y;

        mat[i].r=std::lower_bound(y+1,y+1+cnt,mat[i].r)-y;

    }

    std::sort(mat+1,mat+1+n);

    for(int i=1;i<=n;i++) if(t==mat[i].id) {t=i;break;}

    int d=mat[t].s;

    change(1,1,cnt,mat[t].l,mat[t].r,mat[t].t-d);

    Time[t]=k;

    for(int i=t+1;i<=n;i++)

    {

        int dis=query(1,1,cnt,mat[i].l,mat[i].r);

        if(dis==-1) continue;

        if(k>=mat[i].s-(dis+d))

        {

            k-=mat[i].s-(dis+d);

            d+=mat[i].s-(dis+d);

            change(1,1,cnt,mat[i].l,mat[i].r,mat[i].t-d);

            Time[i]=k;

        }

        else

            break;

    }

    for(int i=1;i<=n;i++)

        ans[mat[i].id]=mat[i].s+Time[i];

    for(int i=1;i<=n;i++)

        printf("%d ",ans[i]);

    return 0;

}

2018.11.4

相关文章