题解 CF685C 【Optimal Point】

chen_zhe · 2020-04-19 21:26:37 · 题解

CF685C Optimal Point

这个题，我看到的第一眼以为是个三分。因为 x 轴固定一个位置，y 轴固定一个位置，去扫 z 轴，会发现距离是一个单峰的函数，对于 x 轴和 y 轴也类似处理，类似 UVA10228 的处理方式即可。那么我们得到了一个 O(n \log^3 v) 的做法，而且是正确的。但是看一眼数据规模，n=10^5,v=10^{18}，会被卡掉，这就很令人不爽。

然后我们看一眼题意，它是要求距离的最大值最小，而最大值最小又可以提示我们这个题可能需要二分，那么我们就可以很显然地去二分这个最大距离 dis，然后就有 n 组约束条件 |x-x_i|+|y-y_i|+|z-z_i| \leq dis

我们会发现这是个很不好处理的不等式关系组，因为有一堆变量，还套个绝对值。我们考虑拆绝对值，根据正负关系，应该会得到 2^3=8 组不等式关系：

看起来是组很恐怖的式子。考虑移项合并，则有：

其中 l_{1 \dots 4},r_{1 \dots 4} 在后续计算中可被视作常数，分别为：

这里的 \max() 和 \min() 其实本质上是给区间取交集。

我们考虑换元，令 a=-x+y+z,b=x-y+z,c=x+y-z，那么可以代换出

我们还会发现另外一点，就是 a,b,c 的奇偶性是一致的，因为 a,b,c 的奇偶性取决于 x,y,z 的奇偶性，符号只是增加或者减少了两倍的 x 或 y 或 z，不影响对 2 取模的余数。这也就告诉了我们，其实我们可以去枚举 a \bmod 2，这样可以再换元：

这样我们再带回第二个不等式组，则有：

那么问题就在于如何求解这个不等式组了。其实也不要想得太复杂，因为我们只要求出一组解，所以可以考虑我们平时做数学题的策略：令 a'=l_2',b'=l_3',c'=l_4'，这样可以保证后三个不等式的约束，然后再看这个时候的 a'+b'+c' 是否满足 l_1' \leq a'+b'+c' \leq l_2'，若满足就是一组解；

若不满足条件，而且 a'+b'+c' < l_1'，我们就可以考虑，在不超过后三组约束条件的同时，适当增加一下 a',b',c' 的大小，也就是先加 a'，如果 a' 被加到最大还不满足 l_1'，就去加 b'，以此类推即可。如果是 a'+b'+c' > r_1' 那么就无解了。

最后的时间复杂度应该是 O(n \log_2 v) 了，比开场的那个三分不知道快到哪里去了。注意一下 C++ 特色取模可能造成一些意想不到的诡异问题。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
#include <vector>

using namespace std;

inline long long read()
{
    long long x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n;

long long x[100050],y[100050],z[100050],xans,yans,zans;

inline void Init()
{
    for (int i=1;i<=n;i++)
        x[i]=y[i]=z[i]=0;
    //memset(x,0,sizeof(x));
    //memset(y,0,sizeof(y));
    //memset(z,0,sizeof(z));
    xans=yans=zans=0;
}

inline bool check(long long mid)
{
    long long r1=4e18,r2=4e18,r3=4e18,r4=4e18;
    long long l1=-4e18,l2=-4e18,l3=-4e18,l4=-4e18;
    for (int i=1;i<=n;i++)
    {
        r1=min(r1,mid+x[i]+y[i]+z[i]);
        r2=min(r2,mid-x[i]+y[i]+z[i]);
        r3=min(r3,mid+x[i]-y[i]+z[i]);
        r4=min(r4,mid+x[i]+y[i]-z[i]);
        l1=max(l1,-mid+x[i]+y[i]+z[i]);
        l2=max(l2,-mid-x[i]+y[i]+z[i]);
        l3=max(l3,-mid+x[i]-y[i]+z[i]);
        l4=max(l4,-mid+x[i]+y[i]-z[i]);
    }
    for (int i=0;i<=1;i++)
    {
        long long l11=l1+((l1&1)^i);
        long long r11=r1-((r1&1)^i);
        long long l21=l2+((l2&1)^i);
        long long r21=r2-((r2&1)^i);
        long long l31=l3+((l3&1)^i);
        long long r31=r3-((r3&1)^i);
        long long l41=l4+((l4&1)^i);
        long long r41=r4-((r4&1)^i);
        if (l11<=r11 && l21<=r21 && l31<=r31 && l41<=r41)
        {
            long long a=l21;
            long long b=l31;
            long long c=l41;
            if (a+b+c<=r11)
            {
                if (a+b+c<l11)
                {
                    if (r21<l11-b-c)
                        a=r21;
                    else
                        a=l11-b-c;
                }
                if (a+b+c<l11)
                {
                    if (r31<l11-a-c)
                        b=r31;
                    else
                        b=l11-a-c;
                }
                if (a+b+c<l11)
                {
                    if (r41<l11-a-b)
                        c=r41;
                    else
                        c=l11-a-b;
                }
                if (a+b+c>=l11)
                {
                    xans=(b+c)>>1;
                    yans=(a+c)>>1;
                    zans=(a+b)>>1;
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main()
{
    int T=read();
    while (T--)
    {
        n=read();
        Init();
        for (int i=1;i<=n;i++)
        {
            x[i]=read();
            y[i]=read();
            z[i]=read();
        }
        if (n==1)
        {
            cout << x[1] << " " << y[1] << " " << z[1] << endl;
            continue;
        }
        long long left=0,right=4e18;
        while (left<=right)
        {
            long long mid=(left+right)>>1; 
            if (check(mid))
                right=mid-1;
            else
                left=mid+1;
        }
        cout << xans << " " << yans << " " << zans << endl;
    }
    return 0;
}