UVA1146 Now or later 做题记录

hlsnqdmz · 2025-05-09 17:00:51 · 个人记录

我【数据删除】你【数据删除】，【数据删除】你全家都【数据删除】？【数据删除】一边去，下次我去出题人家里给他带一瓶可乐，不然他家没一个喘气的了。

平心而论，题可以，是练习二分加 2-SAT 的好题，但出题人脑子有问题，把链式前向星卡了，导致我只能用 vector 存图。

看到题目，飞机只有两个选择：早降和晚落，那么很容易看出来我们可以二分加 2-SAT 完成这道题。另外，枚举两架飞机要分别枚举它们的早降和晚落时间比较，小于当前二分值就连边，由于连的边太多导致要用 vector，非常难受。

最后贴出代码：

//Just Sayori
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long
#define rnt register int
#define gr getchar
#define pr putchar
#define N 500005
#define M 10000000
using namespace std;

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

inline void write(ll x)
{
    static int top = 0, sta[39];
    if (x < 0)
        pr('-');
    do
        sta[++top] = x % 10, x /= 10;
    while (x);
    while (top)
        pr(sta[top--] ^ 48);
}

/*struct edge
{
    int v, next;
} e[N << 6];
int head[N], cnt;*/
vector<int> e[N];

inline void add(int u, int v)
{
    e[u].push_back(v);
}
int n, m, ans, bcc, cnt, top;
int a[N], b[N], dfn[N], low[N], num[N], vis[N], ord[N], stack[N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++cnt;
    vis[u] = 1, stack[++top] = u;
    for (rnt i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (!dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        else if (vis[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        bcc++;
        while (stack[top + 1] != u)
            num[stack[top]] = bcc, vis[stack[top--]] = 0;
    }
}

bool work(int k)
{
    for (rnt i = 2; i <= n; i++)
        for (rnt j = 1; j < i; j++)
        {
            if (abs(a[i] - a[j]) < k)
                add(i, j + n), add(j, i + n);
            if (abs(a[i] - b[j]) < k)
                add(i, j), add(j + n, i + n);
            if (abs(b[i] - a[j]) < k)
                add(i + n, j + n), add(j, i);
            if (abs(b[i] - b[j]) < k)
                add(i + n, j), add(j + n, i);
        }
    for (rnt i = 1; i <= 2 * n; i++)
        if (!dfn[i])
            tarjan(i);
    for (rnt i = 1; i <= n; i++)
        if (num[i] == num[i + n])
            return 0;
    return 1;
}

int main()
{
    while (cin >> n)
    {
        for (rnt i = 1; i <= n; i++)
            a[i] = read(), b[i] = read();
        int l = 0, r = M;
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;
            if (work(mid))
                ans = mid, l = mid;
            else
                r = mid - 1;
            for (rnt i = 1; i <= 2 * n; i++)
                dfn[i] = num[i] = vis[i]  = stack[i] = 0, e[i].clear();//二分不清空，亲人两行泪
            bcc = cnt = top = 0;
        }
        write(ans), pr(10);
        for (rnt i = 1; i <= 2 * n; i++)
            dfn[i] = num[i] = vis[i] = stack[i] = 0, e[i].clear();、、多测不清空，亲人两行泪。
        bcc = cnt = top = 0;
    }
    return 0;
}