抢了个一血。不懂啊，这么傻逼的题居然没有人在
52
min
52 \min
52
min
内切（我如果小细节不写挂就十分钟切了）。
题目描述
给你若干个三元组
(
a
i
,
b
i
,
c
i
)
(a_i,b_i,c_i)
(
a
i
,
b
i
,
c
i
)
和
(
a
i
′
,
b
i
′
,
c
i
′
)
(a_i’,b_i’,c_i’)
(
a
i
′
,
b
i
′
,
c
i
′
)
。
你可以从
(
a
i
,
b
i
,
c
i
)
(a_i,b_i,c_i)
(
a
i
,
b
i
,
c
i
)
和
(
a
i
′
,
b
i
′
,
c
i
′
)
(a_i’,b_i’,c_i’)
(
a
i
′
,
b
i
′
,
c
i
′
)
中选择一个三元组作为第
i
i
i
个三元组（
a
i
′
≥
a
i
,
b
i
′
≥
b
i
,
c
i
′
≥
c
i
a_i’ \ge a_i,b_i’ \ge b_i,c_i’ \ge c_i
a
i
′
≥
a
i
,
b
i
′
≥
b
i
,
c
i
′
≥
c
i
）。
设你最后选择的三元组是
(
A
i
,
B
i
,
C
i
)
(A_i,B_i,C_i)
(
A
i
,
B
i
,
C
i
)
。
那么这种方案的权值就是
max
(
max
A
i
−
min
A
i
,
max
B
i
−
min
B
i
,
max
C
i
−
min
C
i
)
\max(\max A_i-\min A_i,\max B_i – \min B_i,\max C_i- \min C_i)
max
(
max
A
i
−
min
A
i
,
max
B
i
−
min
B
i
,
max
C
i
−
min
C
i
)
。
你需要找出一种方案，使得权值最小，并输出最小权值。
思路
看到最大值最小，直接二分。
考虑如何
c
h
e
c
k
\rm check
check
。
我们把
(
a
i
,
b
i
,
c
i
)
(a_i,b_i,c_i)
(
a
i
,
b
i
,
c
i
)
和
(
a
i
′
,
b
i
′
,
c
i
′
)
(a_i’,b_i’,c_i’)
(
a
i
′
,
b
i
′
,
c
i
′
)
并成一个六元组
(
a
i
,
b
i
,
c
i
,
a
i
′
,
b
i
′
,
c
i
′
)
(a_i,b_i,c_i,a_i’,b_i’,c_i’)
(
a
i
,
b
i
,
c
i
,
a
i
′
,
b
i
′
,
c
i
′
)
，先钦定所有三元组都选
(
a
i
,
b
i
,
c
i
)
(a_i,b_i,c_i)
(
a
i
,
b
i
,
c
i
)
。
搞三个数组：
x
,
y
,
z
x,y,z
x
,
y
,
z
，分别表示这个六元组按
a
i
a_i
a
i
排序，按
b
i
b_i
b
i
排序，按
c
i
c_i
c
i
排序后的结果。
不难发现需要换成
(
a
i
′
,
b
i
′
,
c
i
′
)
(a_i’,b_i’,c_i’)
(
a
i
′
,
b
i
′
,
c
i
′
)
的三元组一定是
x
,
y
,
z
x,y,z
x
,
y
,
z
的一段前缀。
三个指针扫一遍即可。
注意需要判断前面三元组换了之后还是不满足条件的情况。
时间复杂度
O
(
n
log
n
)
\mathcal O(n \log n)
O
(
n
lo
g
n
)
。
代码
//A tree without skin will surely die.
//A man without face is invincible.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(),(x).end()
#define Tim ((double)clock()/CLOCKS_PER_SEC)
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
int const N=1e5+10;
int n,nwx,nwy,nwz,ix,iy,iz,qza,qzb,qzc;
struct node{int a,b,c,d,e,f;}a[N],b[N],c[N];
void push(node x){
nwx=max(nwx,x.d),nwy=max(nwy,x.e),nwz=max(nwz,x.f);
qza=min(qza,x.d),qzb=min(qzb,x.e),qzc=min(qzc,x.f);
}
bool check(int V){
nwx=a[n].a,nwy=b[n].b,nwz=c[n].c,ix=1,iy=1,iz=1,qza=1e9,qzb=1e9,qzc=1e9;
while (1){
if (nwx-a[ix].a<=V && nwy-b[iy].b<=V && nwz-c[iz].c<=V && nwx-qza<=V && nwy-qzb<=V && nwz-qzc<=V) return 1;
while (ix<=n && nwx-a[ix].a>V){push(a[ix]),++ix;if (nwx-qza>V || nwy-qzb>V || nwz-qzc>V) return 0;}
while (iy<=n && nwy-b[iy].b>V){push(b[iy]),++iy;if (nwx-qza>V || nwy-qzb>V || nwz-qzc>V) return 0;}
while (iz<=n && nwz-c[iz].c>V){push(c[iz]),++iz;if (nwx-qza>V || nwy-qzb>V || nwz-qzc>V) return 0;}
if (nwx-qza>V || nwy-qzb>V || nwz-qzc>V) return 0;
}
return 1;
}
void solve(){
cin>>n;
for (int i=1;i<=n;++i) cin>>a[i].a>>a[i].b>>a[i].c>>a[i].d>>a[i].e>>a[i].f;
for (int i=1;i<=n;++i) b[i]=a[i],c[i]=a[i];
sort(a+1,a+n+1,[](node x,node y){return x.a<y.a;});
sort(b+1,b+n+1,[](node x,node y){return x.b<y.b;});
sort(c+1,c+n+1,[](node x,node y){return x.c<y.c;});
int l=0,r=1e9;
while (l<r)
if (check(mid)) r=mid;
else l=mid+1;
cout<<l<<'\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t=1;
cin>>t;
while (t--) solve();
return 0;
}