D. Xenia and Colorful Gems（二分）

Tia ·

更新时间:2024-11-10

· 523 次阅读

题目传送门

题意： 给你na个红色糖，nb个绿色糖，nc个蓝色糖，每一块糖都有自己的一个权值，每种颜色拿一个，使得(x-y)2 + (x-z)2 +(y-z)2 尽可能小，x,y,z表示三块糖的权值。

思路： 我们知道选出的三块糖有 x<=y<=z （只看数值，不看颜色），那么我们枚举所有糖果，作为中间的这个，然后在另外两种糖果中分别找一个大于等于y、小于y的，最后算最小值就行了。

#include
#define endl '\n'
#define null NULL
#define ls p<<1
#define rs p<<1|1
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
#define int long long
#define vi vector
#define mii map
#define pii pair
#define ull unsigned long long
#define all(x) x.begin(),x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
char *fs,*ft,buf[1<<20];
#define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++;
inline int read(){
int x=0,f=1;char ch=gc();
while(ch'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}
return x*f;}
using namespace std;
const int N=2e5+5;
const int inf=0x7fffffff;
const int mod=998244353;
const double eps=1e-6;
int a[N],b[N],c[N];
int check(int i,int j,int k)
{
  //  cout<<i<<' '<<j<<' '<<k<>t;
    while(t--)
    {
        int na,nb,nc;
        cin>>na>>nb>>nc;
        for(int i=1;i>a[i];
        for(int i=1;i>b[i];
        for(int i=1;i>c[i];
        sort(a+1,a+na+1);sort(b+1,b+nb+1);sort(c+1,c+nc+1);
        int res=2e18;
        for(int i=1;i<=na;i++)
        {
            int pb=lower_bound(b+1,b+nb+1,a[i])-b;
            int pc=lower_bound(c+1,c+nc+1,a[i])-c;
            if(pb==nb+1)
                pb--;
            if(pc==nc+1)
                pc--;
            res=min(res,check(i,pb,pc));
            if(pb!=1)
                res=min(res,check(i,pb-1,pc));
            if(pc!=1)
                res=min(res,check(i,pb,pc-1));
            if(pb!=1&&pc!=1)
                res=min(res,check(i,pb-1,pc-1));
        }
        for(int i=1;i<=nb;i++)
        {
            int pa=lower_bound(a+1,a+na+1,b[i])-a;
            int pc=lower_bound(c+1,c+nc+1,b[i])-c;
            if(pa==na+1)
                pa--;
            if(pc==nc+1)
                pc--;
            res=min(res,check(pa,i,pc));
            if(pa!=1)
                res=min(res,check(pa-1,i,pc));
            if(pc!=1)
                res=min(res,check(pa,i,pc-1));
            if(pa!=1&&pc!=1)
                res=min(res,check(pa-1,i,pc-1));
        }
        for(int i=1;i<=nc;i++)
        {
            int pb=lower_bound(b+1,b+nb+1,c[i])-b;
            int pa=lower_bound(a+1,a+na+1,c[i])-a;
            if(pb==nb+1)
                pb--;
            if(pa==na+1)
                pa--;
            res=min(res,check(pa,pb,i));
            if(pb!=1)
                res=min(res,check(pa,pb-1,i));
            if(pa!=1)
                res=min(res,check(pa-1,pb,i));
            if(pb!=1&&pa!=1)
                res=min(res,check(pa-1,pb-1,i));
        }
        cout<<res<<endl;
    }
}