题解：P2632 Explorer

Firsry · 2025-07-17 16:59:33 · 题解

人类智慧

蒟蒻太弱了，准高二了还不会用直线解析式算垂足，所以就用玄学连边 A 了。

注意到主要矛盾是优化建边，边的数量又是 Kruskal 的命根子，所以我们只连可能比较有用的边。

观察到两条直线 l_1, l_2，l_1 上面的点在 l_2 上的垂足是有单调性的，所以充分发扬人类智慧，设置大小为 108 的观察窗口以及大小为 15 的连边窗口，用于找到最优点，并且在最优点附近（可能有用的点）进行连边。

细节处理

• 为了保证从一端看向另一端，我们需要 sort 一下 t 数组；
• Kruskal 一定是连成一棵树之后 edgeCount = n + m - 1 就 break；
• 时间空间都很极限，我们的匹配点 match 从数组优化为两个滚动变量 pre, match；
• 观察需要比较大，但是连边不是；（本蒟蒻大量的 MLE 来自这一点没有考虑到 qwq）
• double 保证高精，不要管为什么 #define dwb double，因为是彩蛋；

upd：AddRange = 5, SeeRange = 50 既可通过此题，更多的极限数据测试已经没脸再交了 qwq。

代码如下：

#include<bits/stdc++.h>
#define dwb double

using namespace std;

const int AddRange = 15;
const int SeeRange = 108;

const int MAXN = 100055;
const dwb INF = 1e18;

struct Edge {
    int from, to;
    dwb weight;
    bool operator < (const Edge another) const {
        return weight < another.weight;
    }
};

int n, m;
int px[5], py[5];
dwb t1[MAXN], t2[MAXN];
dwb x1_, y1_, x2_, y2_;

int anc[MAXN << 1];

vector<Edge> edge;

inline void AncInit(int siz) {
    for (int i = 1; i <= siz; ++i)
        anc[i] = i;
    return;
}
inline int findAnc(int cur) {
    if (cur != anc[cur])
        anc[cur] = findAnc(anc[cur]);
    return anc[cur];
}
inline void merge(int a, int b) {
    anc[findAnc(a)] = findAnc(b);
}

inline dwb calX(dwb t, int p1, int p2) {
    return px[p1] * t + px[p2] * (1 - t);
}
inline dwb calY(dwb t, int p1, int p2) {
    return py[p1] * t + py[p2] * (1 - t);
}
inline dwb calDis() {
    return sqrt((x1_ - x2_) * (x1_ - x2_) + (y1_ - y2_) * (y1_ - y2_));
}

inline void kruskal() {
    dwb mst = 0;
    sort(edge.begin(), edge.end());
    AncInit(n + m);
    int edgeCount = 0, aim = n + m - 1;
    for (Edge e : edge) {
        int ancFrom = findAnc(e.from);
        int ancTo = findAnc(e.to);
        if (ancFrom != ancTo) {
            merge(ancFrom, ancTo);
            mst += e.weight;
            edgeCount++;
            if (edgeCount == aim)
                break;
        }
    }
    printf("%.3lf", mst);
}

inline void init() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= 4; ++i)
        scanf("%d%d", &px[i], &py[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%lf", &t1[i]);
    for (int i = 1; i <= m; ++i)
        scanf("%lf", &t2[i]);

    sort(t1 + 1, t1 + 1 + n);
    sort(t2 + 1, t2 + 1 + m);

    for (int i = 2; i <= n; ++i) {
        x1_ = calX(t1[i - 1], 1, 2);
        y1_ = calY(t1[i - 1], 1, 2);
        x2_ = calX(t1[i], 1, 2);
        y2_ = calY(t1[i], 1, 2);
        edge.push_back({i - 1, i, calDis()});
    }
    for (int i = 2; i <= m; ++i) {
        x1_ = calX(t2[i - 1], 3, 4);
        y1_ = calY(t2[i - 1], 3, 4);
        x2_ = calX(t2[i], 3, 4);
        y2_ = calY(t2[i], 3, 4);
        edge.push_back({i - 1 + n, i + n, calDis()});
    }
}

inline void build() {
    int pre = 1, st = 1, ed = m;
    for (int i = 1; i <= n; ++i) {
        x1_ = calX(t1[i], 1, 2);
        y1_ = calY(t1[i], 1, 2);
        if (i != 1) {
            st = max(1, pre - SeeRange);
            ed = min(m, pre + SeeRange);
        }
        dwb minDis = INF;
        int match = st;
        for (int j = st; j <= ed; ++j) {
            x2_ = calX(t2[j], 3, 4);
            y2_ = calY(t2[j], 3, 4);
            dwb dis = calDis();
            if (dis < minDis)
                minDis = dis, match = j;
        }
        pre = match;
        int add_st = max(1, match - AddRange);
        int add_ed = min(m, match + AddRange);
        for (int j = add_st; j <= add_ed; ++j) {
            x2_ = calX(t2[j], 3, 4);
            y2_ = calY(t2[j], 3, 4);
            edge.push_back({i, j + n, calDis()});
        }
    }
}

int main() {
    init();
    build();
    kruskal();
    return 0;
}