codeforces-1337-D Xenia and Colorful Gems

传送门：https://codeforces.com/contest/1337/problem/D

题意：三个数组，每个数组中挑出来一个数，求 (a - b) * (a - b) + (a - c) * (a - c) + (b - c) * (b - c)的最小值
比赛的时候卡了C就跑来做D，一看求这个式子的最小值，那就是一个数组里找到一个数，使他们的差的绝对值最小

（然后我就跑偏了，走上了一条不归路：【错误思路】把他们放到一个vector里排序，然后双指针维护找到一个距离最短的序列这个序列至少包含三个数组的各一个元素，然后这个序列的最左边和最右边一定在他所在的数组是唯一的，遍历中间的数（他们是在一个数组里的）的找最小值，所以我就开开心心的去用双指针维护了，然后就凉凉了，后来反应过来，三个放在一起排序呢，最优的排序方式是穿插着例 a 1 1 2 2 /b 1 1 2 2 /c 1 1 2 2 最优 1a,1b,1c,1a,1b,1c …… 但是你排序是没办法把他排成这样/哭，如果做得到的小伙伴可以去试试我这个想法）

AC思路：一个一个暴力的遍历那指定是要T飞的，仨一起排不行，那就一个一个排序，对于每一组选择 i,j,k 更新i+1,j,k / i,j+1,k / i,j,k+1 三组情况的最小值，并转移最小值的状态，这样保证每次的操作都是能向着最优的方向进行
具体实现看代码吧

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
const ll inf = 5e18;
const int maxn = 200009;
vector<ll> ve[5];
ll solve(ll a, ll b, ll c)
{
    return (a - b) * (a - b) + (a - c) * (a - c) + (b - c) * (b - c);
}
int main()
{
    int _;
 //   freopen("in.in", "r", stdin);
    for (scanf("%d", &_); _; _--)
    {
        for (int i = 0; i < 5; i++)
            ve[i].clear();
        int na, nb, nc;
        ll x;
        scanf("%d%d%d", &na, &nb, &nc);
        for (int i = 1; i <= na; i++)
        {
            scanf("%lld", &x);
            ve[1].push_back(x);
        }
        for (int i = 1; i <= nb; i++)
        {
            scanf("%lld", &x);
            ve[2].push_back(x);
        }
        for (int i = 1; i <= nc; i++)
        {
            scanf("%lld", &x);
            ve[3].push_back(x);
        }
        sort(ve[1].begin(), ve[1].end());
        sort(ve[2].begin(), ve[2].end());
        sort(ve[3].begin(), ve[3].end());
        ll i=0, j=0, k=0;
        ll ans=solve(ve[2][0],ve[1][0],ve[3][0]);
        while (1)
        {
 //           printf("%d %d %d
",i,j,k);
            ll t1=inf,t2=inf,t3=inf;
            if(i>=na||j>=nb||k>=nc) break;
            if(i+1!=na)
            {
                t1=solve(ve[1][i+1],ve[2][j],ve[3][k]);
            }
            if(j+1!=nb)
            {
                t2=solve(ve[1][i],ve[2][j+1],ve[3][k]);
            }
            if(k+1!=nc)
            {
                t3=solve(ve[1][i],ve[2][j],ve[3][k+1]);
            }
            ll minn=min(t1,min(t2,t3));
            ans=min(ans,minn);
            if(minn==t1) i++;
            else if(minn==t2) j++;
            else if(minn==t3) k++;
        }
        printf("%lld
", ans);
    }
    return 0;
}