D. Xenia and Colorful Gems(二分+暴力)

Problem - 1337D - Codeforces

 题意:最近Xenia买了nr红色宝石，ng绿色宝石和nb蓝色宝石。每种宝石都有一个重量。假设所选宝石的重量为x、y和z，Xenia想找到(x-y)2+(y-z)2+(z-x)2的最小值。作为她亲爱的朋友，你能帮助她吗？

题解:

我们要找的钻石重量应该是符合这种规律的 a <= b<= c

那我们就假设现在的是b,二分寻找a与c

将三种宝石重量排序,r,g,b;

void getmin(vecl r, vecl g, vecl b) {
    for (int i = 0; i < r.size(); i++) {
        ll x1 = upper_bound(g.begin(), g.end(), r[i]) - g.begin();
        ll x2 = lower_bound(b.begin(), b.end(), r[i]) - b.begin();
        if (x1 == 0 || x2 == b.size()) continue;
        x1--;
        ll x = r[i], y = g[x1], z = b[x2];
        Min = min(Min, pow2(x - y) + pow2(x - z) + pow2(y - z));
    }
}
 
 
 
        getmin(r, g, b);
        getmin(r, b, g);
        getmin(b, r, g);
        getmin(b, g, r);
        getmin(g, r, b);
        getmin(g, b, r);

大部分人写的核心代码,遍历a很好理解,为什么一个是lower_bound,一个是upper_bound

因为a <= b<= c

要找的是一个在左边,一个在右边,upper_bound后下标又减一代表找的是左边,找右边好说

要换着再找一遍

并且三个都要考虑,所以是六遍

但是代码中这这一部分实在没搞明白

所以我自己写了下面的

		if(x2 == c.size())
		{
			x2--;
		}
		if(x1 == b.size())
		{
			x1--;
		}
		else
		{
			if(x1!=0)
			x1--;
		}

首先判断越界情况,如果有要减,其次x1就是upper_bound找左边的情况,如果没有一个是大于当前的,返回的下标是0,就不能减了;

 

#include
#include
#include
using namespace std;
#define int long long
vector r,g,b;
int mi = 9e18;
int pow2(int x)
{
	return x*x; 
}
void solve(vectora,vectorb,vectorc)
{
	for(int i = 0;i < a.size();i++)
	{
		int x1 = upper_bound(b.begin(),b.end(),a[i])-b.begin();
		int x2 = lower_bound(c.begin(),c.end(),a[i])-c.begin();
		if(x2 == c.size())
		{
			x2--;
		}
		if(x1 == b.size())
		{
			x1--;
		}
		else
		{
			if(x1!=0)
			x1--;
		}
		mi = min(mi,pow2(a[i]-b[x1])+pow2(a[i]-c[x2])+pow2(b[x1]-c[x2]));
	}
}
signed main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int nr,ng,nb;
		cin >> nr >>ng >> nb;
		r.clear();
		g.clear();
		b.clear();
		for(int i = 1;i <= nr;i++)
		{
			int x;
			cin >>x;
			r.push_back(x);
		}
		for(int i = 1;i <= ng;i++)
		{
			int x;
			cin >> x;
			g.push_back(x);
		}
		for(int i = 1;i <= nb;i++)
		{
			int x;
			cin >> x;
			b.push_back(x);
		}
		mi = 9e18;
		sort(r.begin(),r.end());
		sort(g.begin(),g.end());
		sort(b.begin(),b.end());
		solve(r,g,b);
		solve(r,b,g);
		solve(g,r,b);
		solve(g,b,r);
		solve(b,r,g);
		solve(b,g,r);
		cout<<mi<<"\n";
	}
}