0%

[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 写了,然后还抄错了,要完。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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;
}