P7561 [JOISC 2021] 道路の建設案 (Road Construction) (Day2) 题解

经典套路考虑曼哈顿转切比雪夫，将两维坐标的约束分离讨论。设转切比雪夫后第 $i$ 个点的坐标为 $(x_i,y_i)$ ，则此时距离的定义变为： $\text{Dist}(i,j)=\max(|x_i-x_j|,|y_i-y_j|)$ 。

然后求第 $k$ 便宜的问题考虑二分求解，设当前二分到的第 $k$ 便宜的路边权为 $w$ ，即存在至少 $k$ 组 $(i,j)$ 满足 $1\le i<j\le n$ 且 $\text{Dist}(i,j)\le w$ 。而 $\text{Dist}$ 的值形如二维数点问题，因此套路的先对第一维排序，用双指针维护出 $x$ 值满足限制的区间，然后在区间内处理 $y$ 维度：考虑开 set 来维护当前双指针扫描到的区间内所有 $y$ 坐标，然后按 $x$ 坐标从小到大扫描的过程中顺便维护出 set，对当前插入的点 $(x_i,y_i)$ 而言，直接在 set 中找出所有值在 $[y_i-w,y_i+w]$ 区间内的元素的数量。暴力挪迭代器看似时间复杂度是 $O(n^2)$ 的，但是因为只需要判定是否有 $k$ 对合法，所以最多只需要枚举到 $k$ 个元素即可。单次判定时间复杂度为 $O(n\log n+k)$ ，总时间复杂度为 $O(n\log^2n+k\log n)$ 可以通过该题。

// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000010;
const int inf = 1e18;
const int mod = 998244353;

inline int power(int a, int b, int c)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % c;
        a = a * a % c, b >>= 1;
    }
    return ans;
}
inline int inversion(int x) { return power(x, mod - 2, mod); }

int n, k;
pair<int, int> pnt[N];
set<pair<int, int>> se;

inline int chk(int w)
{
    se.clear();
    int l = 1, r = 0, cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        ++r;
        while (pnt[r].first - pnt[l].first > w)
            se.erase({pnt[l].second, l}), ++l;
        auto it = se.lower_bound({pnt[r].second - w, 0});
        while (it != se.end() && it->first <= pnt[r].second + w)
        {
            ++cnt, ++it;
            if (cnt >= k)
                return 0;
        }
        se.emplace(pnt[r].second, r);
    }
    return cnt < k;
}

inline int dist(int i, int j)
{
    return max(abs(pnt[i].first - pnt[j].first), abs(pnt[i].second - pnt[j].second));
}

signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
    {
        int xx, yy;
        cin >> xx >> yy;
        pnt[i] = {xx + yy, xx - yy};
    }
    sort(pnt + 1, pnt + n + 1, [&](auto &l, auto &r) { return l.first < r.first; });
    int l = 0, r = 5e9, best = -1;
    while (l <= r)
    {
        int mid = l + r >> 1;
        chk(mid) ? (best = mid, l = mid + 1) : (r = mid - 1);
    }
    cerr << "best = " << best << '\n';
    vector<int> res;
    if (~best)
    {
        se.clear();
        int l = 1, r = 0;
        for (int i = 1; i <= n; ++i)
        {
            ++r;
            while (pnt[r].first - pnt[l].first > best)
                se.erase({pnt[l].second, l}), ++l;
            auto it = se.lower_bound({pnt[r].second - best, 0});
            while (it != se.end() && it->first <= pnt[r].second + best)
                res.emplace_back(dist(r, it->second)), ++it;
            se.emplace(pnt[r].second, r);
        }
    }
    while (res.size() < k)
        res.emplace_back(best + 1);
    sort(res.begin(), res.end());
    for (int &i : res)
        cout << i << '\n';
    return 0;
}

隐藏／恢复文章

随机文章