Solution. CF1336B Xenia and Colorful Gems

Description

给出三个正整数序列 $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,b_i,g_i\le10^9,1\le n_r,n_g,n_b\le10^5$

Solution

我们显然希望 $x,y,z$ 尽可能接近，但是并不容易找到一种正确的贪心思路。

为了简化问题，我们现在钦定 $x\le y\le z$，考虑枚举其中一个数，然后去找使答案最优的另外两个数。

如果我们枚举 $x$，并且选择最小的 $\ge x$ 的 $y$，最小的 $\ge y$ 的 $z$，这样做正确性是没有保障的，如果我们固定 $z$，找到一个较大的 $y$ 均摊 $x-y$ 与 $y-z$，答案就会更优。同理也不能枚举 $z$。

考虑枚举 $y$，此时可以找一个最大的 $\le y$ 的 $x$，最小的 $\ge y$ 的 $z$，不难发现这样一定最优，双指针维护一下就能够做到 $O(n)$。

由于我们无法知道 $x,y,z$ 之间的大小关系，我们只需要考虑所有的 $3!=6$ 种情况即可。

总复杂度 $O(n\log n)$，瓶颈在排序。

Code

namespace Main{
    const int N = 100005;
    int T, na, nb, nc;
    ll ans;
    vector<int> a, b, c;
    LL s(int x) { return 1ll * x * x; }
    void solve(vector<int> a, vector<int> b, vector<int> c){
        for(ri i = 0, j = 0, k = 0; i < b.size(); i++){
            while(j < a.size() - 1 && a[j + 1] <= b[i]) j++;
            while(k < c.size() - 1 && c[k] < b[i]) k++;
            if(a[j] > b[i] || c[k] < b[i]) continue;
            ans = min(ans, s(b[i]-a[j]) + s(c[k]-b[i]) + s(c[k]-a[j]));
        }
    }
    void Main(){
        input(T);
        while(T--){
            input(na, nb, nc);
            a.resize(na), b.resize(nb), c.resize(nc);
            for(ri i = 0; i < na; i++) input(a[i]);
            for(ri i = 0; i < nb; i++) input(b[i]);
            for(ri i = 0; i < nc; i++) input(c[i]);
            sort(a.begin(), a.end());
            sort(b.begin(), b.end());
            sort(c.begin(), c.end());
            ans = 9e18;
            solve(a, b, c), solve(a, c, b);
            solve(b, a, c), solve(b, c, a);
            solve(c, a, b), solve(c, b, a);
            write(ans), puts("");
        }
        return;
    }
} // namespace

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。