题解：P1728 [PA 2014] Parking

· · 题解

一些废话：

这是我的第3篇题解，求管理大大过QwQ。dalao勿喷，有错误请私信我，我会及时改正。也在这里求个小小的关注。

问题分析

车辆只能在宽度为 w 的无限长矩形停车场内平移，不能旋转，且移动过程中不能相互碰撞。由于停车场向右无限延伸，车辆在水平方向有足够的调整空间，真正的限制来自垂直方向。

当两辆车在移动过程中需要“交叉”时，即它们的初始位置和目标位置在水平方向上的相对顺序发生了变化，这两辆车在垂直方向上的宽度之和就不能超过停车场的宽度 w。否则，在某个时刻它们必然会发生碰撞。

算法思路（重点来了！）

处理坐标：

确保每辆车的坐标满足 x_1 \le x_2 和 y_1 \le y_2，并计算每辆车的宽度 w_i = y_2 - y_1。排序：将初始位置和目标位置的车分别按照左下角坐标 (x_1, y_1) 排序，优先按 x_1 排序，x_1 相同时按 x_2 排序。

建立映射：

记录每辆车在初始排序中的排名，然后按照目标排序的逆序处理车辆。

树状数组维护：

使用树状数组维护已处理车辆的最大宽度。对于当前处理的车，查询在初始排序中排名在其之前的车辆的最大宽度，如果这个宽度加上当前车的宽度大于 w，则移动不可行；否则更新树状数组。一定要理解，不然没法写！

AC代码（你们的最爱）

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
struct Matrix {
    int x1, x2, w, id;
} a1[N], a2[N];
int n, T, W, pos[N], bit[N];
inline int lowbit(int x) { return x & -x; }
inline void update(int x, int v) {
    for (int i = x; i; i -= lowbit(i))
        bit[i] = max(bit[i], v);
}
inline int query(int x) {
    int ret = 0;
    for (int i = x; i <= n; i += lowbit(i))
        ret = max(ret, bit[i]);
    return ret;
}
inline bool cmp(const Matrix &a, const Matrix &b) {
    return a.x1 == b.x1 ? a.x2 < b.x2 : a.x1 < b.x1;
}
inline int read() {
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    int x = 0;
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
int main() {
    T = read();
    while (T--) {
        n = read(), W = read();
        for (int i = 1, y1, y2; i <= n; ++i) {
            a1[i].x1 = read(), y1 = read(), a1[i].x2 = read(), y2 = read();
            a1[i].id = i;
            if (a1[i].x1 > a1[i].x2) swap(a1[i].x1, a1[i].x2);
            a1[i].w = abs(y1 - y2);
        }
        for (int i = 1, y1, y2; i <= n; ++i) {
            a2[i].x1 = read(), y1 = read(), a2[i].x2 = read(), y2 = read();
            a2[i].id = i;
            if (a2[i].x1 > a2[i].x2) swap(a2[i].x1, a2[i].x2);
            a2[i].w = abs(y1 - y2);
        }
        bool f = 1;
        sort(a1 + 1, a1 + n + 1, cmp);
        sort(a2 + 1, a2 + n + 1, cmp);

        for (int i = 1; i <= n; ++i) pos[a1[i].id] = i;

        for (int i = 1; i <= n; ++i) {
            if (query(pos[a2[i].id]) + a2[i].w > W) {
                f = false;
                break;
            }
            update(pos[a2[i].id], a2[i].w);
        }

        fill(bit + 1, bit + n + 1, 0);
        puts(f ? "TAK" : "NIE");
    }
    return 0//注意了
}

看过读过，一定赞过QAQ