[CF1336B] Xenia and Colorful Gems

题目

题目链接

题目大意：$t$ 组数据。给出长度为 $n_r, n_g, n_b$ 的序列 $r, g, b$，要求在三个序列中各选一个数 $x, y, z$，使得 $(x - y) ^ 2 + (y - z) ^ 2 + (z - x) ^ 2$ 最小。$1 \le t \le 100, 1 \le n_r, n_g, n_b \le 10^5, 1 \le r_i, g_i, b_i \le 10^9$。时限 3s。

思路

最简单的做法肯定是 $n^3$ 枚举，写的快跑得慢。

如果只有两个序列的话，显然可以枚举 $r$ 中的所有数，然后每次二分找 $g$ 中和它差最小的数。

对于这个题也一样：枚举 $r$ 中的所有数，然后二分找 $g$ 和 $b$ 中离他最近的数。

但是这里有个问题：怎么确定找 $z$ 的时候是离 $y$ 更近还是离 $x$ 更近呢？

我们发现不用考虑，都试一遍就行了。

总共可能的顺序有 $6$ 种，再看到给了 3s，能过。

这题昨天晚上写的我越写越困，最后干脆直接照着 std 写了，然后还抄错了，要完。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return;
}

typedef long long LL;

std::vector<LL> r, g, b;
LL ans, nr, ng, nb, t, p;

void solve(std::vector<LL> a, std::vector<LL> b, std::vector<LL> c) {
    for (auto x : a) {
        auto y = std::lower_bound(b.begin(), b.end(), x), z = std::upper_bound(c.begin(), c.end(), x);
        if (y == b.end() || z == c.begin())   continue;
        --z;
        ans = std::min(ans, (x - *y) * (x - *y) + (*y - *z) * (*y - *z) + (x - *z) * (x - *z));
    }
}

int main() {
    read(t);
    while (t--) {
        ans = 9e18;
        r.clear(), g.clear(), b.clear();
        read(nr), read(ng), read(nb);
        for (int i = 1; i <= nr; ++i)   read(p), r.push_back(p);
        for (int i = 1; i <= ng; ++i)   read(p), g.push_back(p);
        for (int i = 1; i <= nb; ++i)   read(p), b.push_back(p);
        std::sort(r.begin(), r.end()), std::sort(g.begin(), g.end()), std::sort(b.begin(), b.end());
        solve(r, g, b), solve(r, b, g), solve(g, r, b), solve(g, b, r), solve(b, r, g), solve(b, g, r);
        printf("%lld\n", ans);
    }
    return 0;
}