自动搬运

查看原文

来自洛谷，原作者为

	b6e0_ ‪

搬运于2025-08-24 22:20:48，当前版本为作者最后更新于2021-07-08 18:37:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这题因为值域很小，所以可以三维前缀和（容斥）做。将一支蜡笔看作三维空间中的一个点 $(R_i,G_i,B_i)$。二分答案，设二分到了 $M$，枚举这三维区间的左端点 $i,j,k$，那么对点 $(x,y,z)$ 的限制就是 $x\in[i,i+M],y\in[j,j+M],z\in[k,k+M]$，用三维前缀和 $\mathcal O(1)$ 求出在这个空间内的点数，判断够不够即可。

对于构造方案，在判断时记下是哪个区间中的点数不小于这个答案，构造时扫描 $n$ 个点判断是否在这个区间即可。

三维前缀和的预处理公式是:

$$s_{i,j,k}=s_{i-1,j,k}+s_{i,j-1,k}+s_{i,j,k-1}-s_{i,j-1,k-1}-s_{i-1,j,k-1}-s_{i-1,j-1,k}+s_{i-1,j-1,k-1}+a_{i,j,k} $$

使用三维前缀和表示第一维在 $[i_1,i_2]$，第二维在 $[j_1,j_2]$，第三维在 $[k_1,k_2]$ 的点数为：

$$s_{i_2,j_2,k_2}-s_{i_1,j_2,k_2}-s_{i_2,j_1,k_2}-s_{i_2,j_2,k_1}+s_{i_2,j_1,k_1}+s_{i_1,j_2,k_1}+s_{i_1,j_1,k_2}-s_{i_1,j_1,k_1} $$

设 $R_i,G_i,B_i$ 的值域为 $m$，时间复杂度 $\mathcal O(m^3\log m)$。代码：

#include<bits/stdc++.h>
using namepace std;
int m,a[260][260][260],s[260][260][260],R[100010],G[100010],B[100010],ansi,ansj,ansk;
inline int read()
{
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x;
}
void write(int x)
{
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}
inline bool check(int M)
{
	for(int i=1;i+M<257;i++)//之所以i,j,k<=256-M是因为假如i超过了，那么点数明显小于为256-M的情况（区间更小）
		for(int j=1;j+M<257;j++)
			for(int k=1;k+M<257;k++)
				if(s[i+M][j+M][k+M]-s[i-1][j+M][k+M]-s[i+M][j-1][k+M]-s[i+M][j+M][k-1]+s[i+M][j-1][k-1]+s[i-1][j+M][k-1]+s[i-1][j-1][k+M]-s[i-1][j-1][k-1]>=m)
				{
					ansi=i;
					ansj=j;
					ansk=k;//记录下可行的区间
					return true;
				}
	return false;
}
int main()
{
	int n=read(),i,j,k,L=-1,r=255,M;
	m=read();
	for(i=1;i<=n;i++)
	{
		R[i]=read();
		G[i]=read();
		B[i]=read();
		a[R[i]+1][G[i]+1][B[i]+1]++;//这里把坐标+1是避免下标越界
	}
	for(i=1;i<257;i++)
		for(j=1;j<257;j++)
			for(k=1;k<257;k++)
				s[i][j][k]=s[i-1][j][k]+s[i][j-1][k]+s[i][j][k-1]-s[i-1][j-1][k]-s[i-1][j][k-1]-s[i][j-1][k-1]+s[i-1][j-1][k-1]+a[i][j][k];
	while(L+1<r)
	{
		M=(L+r)>>1;
		if(check(M))
			r=M;
		else
			L=M;
	}
	ansi--;
	ansj--;
	ansk--;
	write(r);
	putchar('\n');
	for(i=1;i<=n;i++)
		if(m&&ansi<=R[i]&&R[i]<=ansi+r&&ansj<=G[i]&&G[i]<=ansj+r&&ansk<=B[i]&&B[i]<=ansk+r)
		{
			write(R[i]);
			putchar(' ');
			write(G[i]);
			putchar(' ');
			write(B[i]);
			putchar('\n');
			m--;
		}
	return 0;
}