CF685C题解

Stay_Hungry · 2021-10-06 18:12:24 · 题解

话说咋就没人想把O(nlogW)稍微改一下优化成O(n)吗

具体做法我这里就不赘述了，细心的人或许早已发现原本几篇题解的判断部分的O(n)完全可以放在二分外提前预处理好，然后判断就成了O(1)（常数不计）了

由于O(klogW)<O(n)所以时间复杂度近似于O(n)

code :

#include <bits/stdc++.h>
#define int long long
#define TOT (TL[1] + TL[2] + TL[3]) 

using namespace std;

const int N = 1e5 + 5, Inf = 4e18;

struct scan {
    char c; bool f;
    inline scan& operator >> (int &x) {
        x = f = 0; for(; !isdigit(c); c = getchar()) f |= (c == '-');
        for(; isdigit(c); c = getchar()) x = x * 10 + c - '0';
        if(f) x = -x; return *this;
    }
} io;

void Min(int &x, int y) {if(x > y) x = y;}
void Max(int &x, int y) {if(x < y) x = y;}

int t, n, x[N], y[N], z[N], A[4], B[4], T[4], L[4], R[4], TL[4], TR[4], ans[4];

// L0 <= x + y + z <= R0
// L1 <= - x + y + z <= R1
// L2 <= x - y + z <= R2
// L3 <= x + y - z <= R3
// a = -x + y + z
// b = x - y + z
// c = x + y - z
// x + y + z = a + b + c

bool over() {
    for(int k = 0; k <= 3; ++k)
        if(TL[k] > TR[k]) return 1;
    return 0;
}

bool judge(int dis) {
    for(int k = 0; k <= 3; ++k)
        R[k] = dis + A[k],
        L[k] = B[k] - dis;
    for(int bit = 0; bit <= 1; ++ bit) {
        for(int k = 0; k <= 3; ++k)
            TL[k] = L[k] + ((L[k] & 1) ^ bit),
            TR[k] = R[k] - ((R[k] & 1) ^ bit);
        if(over()) continue;
        if(TR[0] < TOT) continue;
        for(int k = 1; k <= 3; ++k)
            if(TOT < TL[0]) TL[k] = min(TR[k], TL[0] + TL[k] - TOT);
        if(TOT < TL[0]) continue;
        ans[1] = (TL[2] + TL[3]) / 2;
        ans[2] = (TL[1] + TL[3]) / 2;
        ans[3] = (TL[1] + TL[2]) / 2;
        return 1;
    }
    return 0;
}

signed main() {
    io >> t;
    while(t --) {
        io >> n;
        for(int i = 1; i <= n; ++i)
            io >> x[i] >> y[i] >> z[i];
        for(int k = 0; k <= 3; ++k)
            A[k] = Inf, B[k] = -Inf;
        for(int i = 1; i <= n; ++i) {
            T[0] = x[i] + y[i] + z[i];
            T[1] = y[i] - x[i] + z[i];
            T[2] = x[i] - y[i] + z[i];
            T[3] = x[i] - z[i] + y[i];
            for(int k = 0; k <= 3; ++k)
                Min(A[k], T[k]),
                Max(B[k], T[k]);
        } //提前预处理
        int l = 0, r = Inf, mid;
        while(l <= r) {
            mid = (l + r) >> 1;
            if(judge(mid)) r = mid - 1;
            else l = mid + 1;
        }
        for(int i = 1; i <= 3; ++i) printf("%lld ", ans[i]); putchar('\n');
    }
    return 0;
}