Xenia and Colorful Gems

题意

给出三个数组，在每个数组中选择一个数字x,y,z,，使得\((x-y)^2+(y-z)^2+(x-z)^2\)最小。

思路

我们假设x<=y<=z

枚举所有的数作为y时，可以取得的最小值。

具体实现：使用vectorvec[4]存三个数组里的数字。

定义一个数组arr[]={1,2,3}，对它进行全排列，每次枚举vec[arr[2]]里的元素作为y,vec[arr[1]]里的元素作为x，vec[arr[3]]里的元素作为z。

x取第一个<=y的，z取第一个>=y的。

代码

#include<bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;

const int N=1e6+10;

const ll inf=0x3f3f3f3f3f3f3f3f;

vector<int>vec[10];

int num[5],arr[4];

int Min(int x,int pos)

{

    int l=0,r=vec[pos].size()-1,ans=-1;

    while(l<=r)

    {

        int mid=(l+r)/2;

        if(vec[pos][mid]<=x)

        {

            ans=vec[pos][mid];

            l=mid+1;

        }

        else

            r=mid-1;

    }

    return ans;

}

ll cal(int a,int b,int c)

{

    return 1LL*(a-b)*(a-b)+1LL*(a-c)*(a-c)+1LL*(b-c)*(b-c);

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        for(int i=1; i<=3; i++)

            scanf("%d",&num[i]);

        for(int i=1; i<=3; i++)

        {

            for(int j=1; j<=num[i]; j++)

            {

                int x;

                scanf("%d",&x);

                vec[i].pb(x);

            }

            sort(vec[i].begin(),vec[i].end());

        }

        for(int i=1; i<4; i++)

            arr[i]=i;

        ll ans=inf;

        do

        {

            int l=arr[1],m=arr[2],r=arr[3];

            for(int x:vec[m])

            {

                int index=lower_bound(vec[l].begin(),vec[l].end(),x)-vec[l].begin();

                int lmax=-1;

                if(index<vec[l].size())

                    lmax=vec[l][index];

                int rmin=Min(x,r);

                if(lmax!=-1&&rmin!=-1)

                    ans=min(ans,cal(x,rmin,lmax));

            }

        }

        while(next_permutation(arr+1,arr+4));

        printf("%lld\n",ans);

        for(int i=1;i<=3;i++)

            vec[i].clear();

    }

    return 0;

}

博客

巴特西

CF #635D Xenia and Colorful Gems 枚举+二分

Xenia and Colorful Gems

题意

思路

代码

最新文章

热门文章