\(\texttt{ABC}\) 生日收到 \(N\) 支蜡笔,每支蜡笔的颜色是三原色红绿蓝的组合,第 \(i\) 个蜡笔的颜色用 \(R_i\) 表示红色,\(G_i\) 表示绿色,\(B_i\) 表示蓝色。
蜡笔 \(i\) 和蜡笔 \(j\) 的颜色差异定义为 \(\max(|R_i-R_j|,|G_i-G_j|,|B_i-B_j|)\),多支蜡笔的颜色差异定义为其中任意两个蜡笔颜色的最大差异值。
\(\texttt{ABC}\) 想从 \(N\) 支蜡笔中选出 \(K\) 支出来,要求这 \(K\) 支蜡笔的颜色差异值最小。
\(color \leq 255,K \leq N \leq 10^5\)
考虑二分一个最小差异值 \(mid\),然后在 \(mid\) 里找到以每一个第一关键字,第二关键字,第三关键字的合法个数,这些东西用三维前缀和搞一搞就可以了,时间复杂度 \(O(color^3 \log color)\)。
Uses math;Consttotal=255;varadd:array[-1..total,-1..total,-1..total] of longint;i,j,p,n,k,x,y,z,l,r,mid:longint;function Check(mid:longint):boolean;
var tmp:longint;
beginCheck:=False;for i:=1 to total do for j:=1 to total do for p:=1 to total dobeginx:=min(total,i+mid); y:=min(total,j+mid); z:=min(total,p+mid);tmp:=add[x,y,z]-add[i-1,y,z]-add[x,j-1,z]-add[x,y,p-1]-add[i-1,j-1,p-1];inc(tmp,add[i-1,j-1,z]+add[i-1,y,p-1]+add[x,j-1,p-1]);if (tmp>=k) then exit(True);end;
end;procedure Ready;
beginread(n,k);for i:=1 to n do begin read(x,y,z); inc(add[x,y,z]); end;for i:=1 to total do for j:=1 to total do for p:=1 to total dobegininc(add[i,j,p],add[i-1,j,p]+add[i,j-1,p]+add[i,j,p-1]+add[i-1,j-1,p-1]);dec(add[i,j,p],add[i-1,j-1,p]+add[i-1,j,p-1]+add[i,j-1,p-1]);end;
end;beginReady;l:=0; r:=trunc(total*1.1);while abs(l-r)>0.1 dobeginmid:=(l+r) >> 1;if Check(mid) then r:=mid else l:=mid+1;end;writeln(l);
end.
