MENU

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
Last Modified: March 26, 2022
Archives Tip
QR Code for this page
Tipping QR Code