『妙不可言系列1』CF635D：Xenia and Colorful Gems

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

Xenia is a girl being born a noble. Due to the inflexibility and harshness of her family, Xenia has to find some ways to amuse herself.

Recently Xenia has bought $n_r$ red gems, $n_g$ green gems and $n_b$ blue gems. Each of the gems has a weight.

Now, she is going to pick three gems.

Xenia loves colorful things, so she will pick exactly one gem of each color.

Xenia loves balance, so she will try to pick gems with little difference in weight.

Specifically, supposing the weights of the picked gems are $x$ , $y$ and $z$ , Xenia wants to find the minimum value of $(x?y{)}^2+(y?z{)}^2+(z?x{)}^2$ . As her dear friend, can you help her?

给定三个正整数数列 $r,g,b$，长度分别为 $n_r,n_g,n_b$。

您需要在三个数列中各取一个整数 $x,y,z$，使得 $(x?y{)}^2+(y?z{)}^2+(z?x{)}^2$ 最小。

多组测试数据，$1\le r_i,g_i,b_i\le 10^9$，$1\le n_r,n_g,n_b\le 10^5$，$1\le \sum n_r,\sum n_g,\sum n_b\le 10^5$。

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

显然尽量相邻可以使得相邻的数尽可能的小，那么我们通过什么手段才能将相邻的所有情况都能枚举到呢？

假设我们在三组中都找到了$x$，$y$和$z$，那么一定是这6种情况之一：
$$\begin{gathered} x\le y\le z \\ x\le z\le y \\ y\le x\le z \\ y\le z\le x \\ z\le x\le y \\ z\le y\le x \end{gathered}$$

然后就可以根据这六种情况去枚举中间那个数字，用双指针维护即可。

$\mathrm{C}\mathrm{o}\mathrm{d}\mathrm{e}$

#include <bits/stdc++.h>
#define int long longusing namespace std;
const int N = 2e5;int a[N], b[N], c[N];int read(void) {
    int s = 0, w = 0;char c = getchar();while (c < '0' || c > '9') w |= c == '-', c = getchar();while (c >= '0' && c <= '9') s = s * 10 + c - 48, c = getchar();return w ? -s : s;
}int val(int a,int b,int c) {
    return a * a + b * b + c * c; 
}int work(int a[N],int b[N],int c[N],int A,int B,int C)
{
    int j = 1, k = 1, res = LONG_LONG_MAX;for (int i=1;i<=A;++i){
    while (j < B && b[j+1] <= a[i]) j ++;while (k < C && c[k] < a[i]) k ++;res = min(res,val(a[i]-b[j],a[i]-c[k],b[j]-c[k])); }return res;
}void work(void)
{
    int A = read(), B = read(), C = read(), res = LONG_LONG_MAX;for (int i=1;i<=A;++i) a[i] = read();for (int i=1;i<=B;++i) b[i] = read();for (int i=1;i<=C;++i) c[i] = read();res = min(res,work(a,b,c,A,B,C));res = min(res,work(a,c,b,A,C,B));res = min(res,work(b,a,c,B,A,C));res = min(res,work(b,c,a,B,C,A));res = min(res,work(c,a,b,C,A,B));res = min(res,work(c,b,a,C,B,A));printf("%lld\n", res); 
}signed main(void)
{
    int T = read();while (T --) work();return 0;
}

$$妙啊(｀?\omega ??)$$