MENU

Solution. CF1336B Xenia and Colorful Gems

Description 展开目录

给出三个正整数序列 r,g,b,长度分别为 nr,ng,nb

要求在三个序列中各取一个数 x,y,z,最小化 (xy)2+(yz)2+(zx)2

1ri,bi,gi109,1nr,ng,nb105

Solution 展开目录

我们显然希望 x,y,z 尽可能接近,但是并不容易找到一种正确的贪心思路。

为了简化问题,我们现在钦定 xyz,考虑枚举其中一个数,然后去找使答案最优的另外两个数。

如果我们枚举 x,并且选择最小的 xy,最小的 yz,这样做正确性是没有保障的,如果我们固定 z,找到一个较大的 y 均摊 xyyz,答案就会更优。同理也不能枚举 z

考虑枚举 y,此时可以找一个最大的 yx,最小的 yz,不难发现这样一定最优,双指针维护一下就能够做到 O(n)

由于我们无法知道 x,y,z 之间的大小关系,我们只需要考虑所有的 3!=6 种情况即可。

总复杂度 O(nlogn),瓶颈在排序。

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: June 5, 2024
Archives Tip
QR Code for this page
Tipping QR Code