题解：P1728 [PA 2014] Parking

· · 题解

题目大意

在一个无限长，宽度为 W 的矩形区域中有 n 个矩形，你可以将每个矩形进行平移，但平移时不能与其他矩形重叠，要求判断能否将每个矩形移动到目标位置，保证初始和目标状态 n 个矩形互不重叠。

思路解析

因为矩形区域的长无限大，所以考虑矩形 u 能否越过矩形 v 到达目标位置时，设 w_{u} 为矩形 u 的宽度，w_{v} 为矩形 v 的宽度，只需保证 w_{u}+w_{v} \leq W 即可。

说明：x_{1, u} 表示矩形 u 的 x_1。

于是考虑怎么判断矩形 u 到达目标位置是否要越过矩形 v，思考一下可以发现，即要同时满足 x_{1, u} \leq x_{1, v} 与 x_{1, v'} \leq x_{1, u'}。

所以我们将矩形按起始位置从小到大排序即可，然后判断是否合法，发现需要维护单点修改，后缀最大值。于是考虑倒着处理，用树状数组维护前缀最大值。

Code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e4+10;
int T;
int n,w;
struct Ma{
    int x1,y1,x2,y2;
    int w,id;
    bool operator <(const Ma& other){
        if(x1==other.x1) return x2<other.x2;
        return x1<other.x1;
    }
}a[N],b[N];

struct Bit{
    int c[N];
    #define lowbit(p) p&-p

    void change(int u,int v){
        for(int i=u;i<=n;i+=lowbit(i))
            c[i]=max(c[i],v);
    }
    int query(int u){
        int ans=0;
        for(int i=u;i;i-=lowbit(i))
            ans=max(ans,c[i]);
        return ans;
    }

    #undef lowbit
}B;

int rnk[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){
        memset(B.c,0,sizeof B.c);
        cin>>n>>w;
        for(int i=1;i<=n;i++){
            cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
            if(a[i].x1>a[i].x2) swap(a[i].x1,a[i].x2);
            if(a[i].y1>a[i].y2) swap(a[i].y1,a[i].y2);
            a[i].id=i;
            a[i].w=a[i].y2-a[i].y1;
        }
        for(int i=1;i<=n;i++){
            cin>>b[i].x1>>b[i].y1>>b[i].x2>>b[i].y2;
            if(b[i].x1>b[i].x2) swap(b[i].x1,b[i].x2);
            if(b[i].y1>b[i].y2) swap(b[i].y1,b[i].y2);
            b[i].id=i;
            b[i].w=b[i].y2-b[i].y1;
        }

        sort(a+1,a+n+1);sort(b+1,b+n+1);
        for(int i=1;i<=n;i++)
            rnk[a[i].id]=i;

        bool ok=true;
        for(int i=n;i>=1;i--){
            if(B.query(rnk[b[i].id])+b[i].w>w){
                ok=false;
                break;
            }
            B.change(rnk[b[i].id],b[i].w);
        }

        if(ok) cout<<"TAK\n";
        else cout<<"NIE\n";
    }
    return 0;
}

注意事项