CodeForces 1408D Searchlights

题意

在二维平面有$n$个海盗，$m$个探照灯，你有两种操作

将所有海盗往上走一步
将所有海盗往右走一步

设海盗为$(a_i,b_i)$，探照灯为$(c_j,d_j)$，当且仅当$a_i\leq c_j$且$b_i\leq d_j$时，海盗在探照灯范围内，问最少多少次操作可以将所有海盗移动到所有探照灯范围外。

分析

将题意抽象一下，找到一个二元组$(x,y)$，$x$表示向上走的步数，$y$表示向右走的步数，然后对于任何海盗$(a_i,b_i)$，都满足加上$(x,y)$后，对于任何探照灯$(c_j,d_j)$要么$a_i+x>c_j$，要么$b_i+y>d_j$，且$x+y$最小。

那么我们$O(nm)$处理，找到海盗和探照灯之间的关系，若海盗在探照灯范围内，得到二元组$(x,y)$，有$a_i+x>c_j$且$b_i+y>d_j$，得到所有二元组后，按照第一维排序。

此时发现，遍历二元组，遍历到第$i$个二元组时，如果取该二元组的$x$，那么$y$最小即为剩余二元组的最大值，这样可以满足前部分探照灯向上走即可脱离，剩余探照灯向右走即可脱离，注意答案初始值是只往右走时的答案。

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define repd(z, x, y) for(int z=x;z>=y;--z)
#define com bool operator<(const node &b)const
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 3e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
pii a[2005], b[2005];
int maxx[2005 * 2005];

void solve() {
    int n, m;
    cin >> n >> m;
    rep(i, 1, n)cin >> a[i].first >> a[i].second;
    rep(i, 1, m)cin >> b[i].first >> b[i].second;
    vector<pii > v;
    rep(i, 1, n) {
        rep(j, 1, m) {
            if (b[j].first < a[i].first || b[j].second < a[i].second)
                continue;
            v.push_back({max(b[j].first + 1 - a[i].first, 0ll), max(0ll, b[j].second + 1 - a[i].second)});
        }
    }
    if (v.empty()) {
        cout << 0;
        return;
    }
    sort(v.begin(), v.end());
    for (int i = v.size() - 1; i >= 0; --i)maxx[i] = max(maxx[i + 1], v[i].second);
    int ans = maxx[0];
    for (int i = 0; i < v.size(); ++i)ans = min(ans, v[i].first + maxx[i + 1]);
    cout << ans;
}


signed main() {
    start;
    while (T--)
        solve();
    return 0;
}