CF1336B Xenia and Colorful Gems 题解

· · 题解

UPD：分析了时间复杂度。修正了笔误（我太弱了把大于写成了小于……）

CF1336B Xenia and Colorful Gems

首先，很显然，要让 (x-y)^2+(y-z)^2+(x-z)^2 的值尽可能小，x,y,z 三个值就要尽可能接近。

于是我们考虑，枚举其中一种宝石的所有重量，然后在另外两种宝石的重量中找到最接近它的值，最后找到最小的答案。

为了便于枚举所有情况，我们可以确定下 x,y,z 的大小关系然后进行枚举。
举个栗子：当我们令 x \le y \le z 时，我们可以先在第一个数组中枚举重量 x ，在第二个数组中找到最接近 x 且大于等于 x 的值 y，在第三个数组中找到最接近 y 且大于等于 y 的值 z。然后计算答案，并在所有的答案中取最小值。

但是由于 x,y,z 的大小关系不确定，我们需要枚举它们的 6 种大小关系，分别是

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

当然，不管是用双指针还是二分都要先排序。

由于要多次用到相同的计算，不妨把枚举和计算的过程放到函数里。然后记得开 long long。

我的做法是双指针，所以没有用 upper_bound 和 lower_bound。

每次找较小值和较大值的部分时间复杂度是 O(n) 的，排序的时间复杂度是 O(n \log n)，所以最终的时间复杂度是 O(n \log n)。

代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
long long r[maxn], g[maxn], b[maxn];
long long ans;

long long calc(long long x, long long y, long long z)
{
    return (x-y)*(x-y)+(y-z)*(y-z)+(x-z)*(x-z);
}

void solve(long long *x, long long *y, long long *z, int nx, int ny, int nz)
{
    int p1 = 0, p2 = 0;
    for(int i = 1; i <= nx; i++)
    {
        while(p1 <= ny && y[p1] <= x[i]) p1++;  //找最接近的较小值
        while(p2 <= nz && z[p2] < x[i]) p2++;  //找最接近的较大值
        if(p1 - 1 != 0 && p2 != nz + 1)  //较小值和较大值都能找到
            ans = min(ans, calc(x[i], y[p1 - 1], z[p2]));
    }
    return;
}

void work()
{
    ans = 0x7fffffffffffffff;  //CF的C++11的编译器不支持<limits.h>中的LONG_LONG_MAX
    int nr, ng, nb;
    scanf("%d%d%d", &nr, &ng, &nb);
    for(int i = 1; i <= nr; i++) scanf("%lld", r + i);
    for(int i = 1; i <= ng; i++) scanf("%lld", g + i);
    for(int i = 1; i <= nb; i++) scanf("%lld", b + i);
    sort(r + 1, r + nr + 1);
    sort(g + 1, g + ng + 1);
    sort(b + 1, b + nb + 1);
   //枚举所有可能的大小关系
    solve(r, g, b, nr, ng, nb);
    solve(r, b, g, nr, nb, ng);
    solve(g, r, b, ng, nr, nb);
    solve(g, b, r, ng, nb, nr);
    solve(b, r, g, nb, nr, ng);
    solve(b, g, r, nb, ng, nr);
    printf("%lld\n", ans);
    return;
}

signed main()
{
    int T;
    scanf("%d", &T);
    while(T--)
        work();
    return 0;
}