题解 P1728 【[PA2014]Parking】

huanyue · 2020-02-13 11:12:06 · 题解

这么前面的题目竟然没有题解,赶紧来占个位

这道题看上去很裸,实际上也很裸

把车车看成矩形

首先使这些矩形不相交

就是一个矩形接一个矩形串起来(羊肉串)

假如两个矩形需要调换的话，那么必须保证,两个矩形的宽相加\leq w 如果都能满足就是合法的,否则不合法

然后就随便维护一下就行了(树状数组/线段树)

摆放顺序的话那么最右是最后一个放的，没有任何障碍，

因此可以采用倒推,从大到小枚举位置,用树状数组维护前缀最值就可以了。

如题解所述,代码也奇短无比

/*
 * @Author: Huanyue 
 * @Date: 2020-02-13 10:42:52 
 * @Last Modified by: Huanyue
 * @Last Modified time: 2020-02-13 11:10:53
 */

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#define rgi register
typedef long long ll;
using namespace std;

const int N = 5e4 + 10;
const int inf = 0x3f3f3f3f;

inline void write(register int x)
{
    if (x < 0)
    {
        putchar('-'), x = -x;
    }
    if (x >= 10)
    {
        write(x / 10);
    }
    putchar('0' + x % 10);
}

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = ((x << 3) + (x << 1) + (ch ^ 48));
        ch = getchar();
    }
    return x * f;
}

struct mat
{
    int x1, y1, x2, y2, width, id;
    friend bool operator<(const mat &a, const mat &b)
    {
        if (a.x1 == b.x1)
            return a.x2 < b.x2;
        return a.x1 < b.x1;
    }
} initial[N], target[N];

int n, w, rk[N];
//树状数组
int tree[N];
inline int lowbit(int x)
{
    return x & (-x);
}
inline void modify(int x, int v)
{
    for (rgi int i = x; i <= n; i += lowbit(i))
        tree[i] = max(tree[i], v);//维护前缀最大值
}
inline int query(int x)
{
    int ret = 0;
    for (int i = x; i; i -= lowbit(i))
        ret = max(ret, tree[i]);
    return ret;
}

int main()
{
    int T = read();
    while (T--)
    {
        memset(tree, 0, sizeof(tree));
        memset(rk, 0, sizeof(rk)); //多组数据,接的memset
        n = read(), w = read();
        for (rgi int i = 1; i <= n; i++)
        {
            initial[i].x1 = read();
            initial[2].y1 = read();
            initial[i].x2 = read();
            initial[i].y2 = read();
            if (initial[i].x1 > initial[i].x2)
                swap(initial[i].x1, initial[i].x2);
            if (initial[i].y1 > initial[i].y2)
                swap(initial[i].y1, initial[i].y2);

            initial[i].id = i;
            initial[i].width = initial[i].y2 - initial[i].y1; //计算宽度
        }
        for (rgi int i = 1; i <= n; i++)
        {
            target[i].x1 = read(), target[i].y1 = read(), target[i].x2 = read(), target[i].y2 = read();
            if (target[i].x1 > target[i].x2)
                swap(target[i].x1, target[i].x2);
            if (target[i].y1 > target[i].y2)
                swap(target[i].y1, target[i].y2);
            target[i].id = i;
            target[i].width = target[i].y2 - target[i].y1;
        }

        sort(initial + 1, initial + n + 1);
        sort(target + 1, target + n + 1);

        for (int i = 1; i <= n; i++)
            rk[initial[i].id] = i;

        bool flag = true;//答案标记

        for (rgi int i = n; i; i--)
        {
            if (query(rk[target[i].id]) + target[i].width > w)
                flag = false;
            if (!flag)
                break;
            modify(rk[target[i].id], target[i].width);
        }
        if (flag)
            puts("TAK");
        else
            puts("NIE");
    }
    return 0;
}