CSES 1742：Robot Path

CSES 1742：Robot Path

題目大意：有一個機器人，初始座標在 $(0, 0)$，之後會要往四個方向其中一個方向走 $x$ 步，如果走到之前走過的地方就要停止，問走幾步會停止。

解法：可以二分搜走的步數，然後可以把走的路變成很多線段，看這些線段有沒有相交。只是如果是可以走完全部，或是和上一步方向相反，那我的作法要減 $1$。然後我的 $\text{code}$ 意外的短，是目前 $\text{CSES}$ 上最短的。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second
 
const int SIZE = 1e5 + 5;
 
int n;
pair<int, int> p[SIZE];
vector<tuple<ll, ll, ll>> vx, vy, op;
multiset<ll> ms;
 
bool ok (ll tot) {
    vx.clear(), vy.clear();
    tot--;
    vx.pb (0, 0, 0);
    ll x = 0, y = 0;
    for (int i = 1; i <= n && tot; i++) {
        auto [d, len] = p[i];
        len = min (1ll * len, tot);
        if (d == 1) vx.pb (x, y + 1, y + len), y += len;
        if (d == 2) vy.pb (y, x - len, x - 1), x -= len;
        if (d == 3) vy.pb (y, x + 1, x + len), x += len;
        if (d == 4) vx.pb (x, y - len, y - 1), y -= len;
        tot -= len;
    }
    sort (vx.begin(), vx.end());
    sort (vy.begin(), vy.end());
    for (int i = 1; i < vx.size(); i++) {
        auto [xi, li, ri] = vx[i];
        auto [xj, lj, rj] = vx[i - 1];
        if (xi == xj && li <= rj) return 0;
    }
    for (int i = 1; i < vy.size(); i++) {
        auto [yi, li, ri] = vy[i];
        auto [yj, lj, rj] = vy[i - 1];
        if (yi == yj && li <= rj) return 0;
    }
    op.clear();
    for (auto [y, l, r] : vy) {
        op.pb (l, y, 1);
        op.pb (r + 1, y, -1);
    }
    sort (op.begin(), op.end());
    int pos = 0;
    ms.clear();
    for (int i = 0; i < vx.size(); i++) {
        auto [x, l, r] = vx[i];
        while (pos < op.size() && x >= get<0> (op[pos])) {
            auto [_, y, t] = op[pos];
            if (t == 1) ms.insert (y);
            else ms.erase (ms.find (y));
            pos++;
        }
        auto lit = ms.lower_bound (l), rit = ms.upper_bound (r);
        if (lit != rit) return 0;
    }
    return 1;
}
 
void solve() {
    cin >> n;
    ll l = 1, r = 1;
    FOR (i, 1, n) {
        char c;
        cin >> c >> p[i].S;
        r += p[i].S;
        if (c == 'U') p[i].F = 1;
        if (c == 'L') p[i].F = 2;
        if (c == 'R') p[i].F = 3;
        if (c == 'D') p[i].F = 4;
    }
    if (ok (r)) {
        cout << r - 1 << '\n';
        return;
    }
    while (l < r) {
        ll mid = (l + r) / 2 + 1;
        if (ok (mid)) l = mid;
        else r = mid - 1;
    }
    for (int i = 1; i <= n; i++) {
        auto [d, len] = p[i];
        if (r == len + 1) {
            auto [dd, llen] = p[i + 1];
            if (d + dd == 5) {
                cout << l - 1 << '\n';
                return;
            }
            break;
        }
        r -= len;
    }
    cout << l << '\n';
}
 
int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！