创建一个500x500的二维数组，每个单元格包含该单元格中粒子数量的计数。然后将该数组与50x50的卷积核卷积，结果数组将在每个单元格中具有50x50区域中粒子的计数。然后找到具有最大值的单元格。
如果您使用50x50的框作为区域，则卷积可以分解为两个独立的卷积，一个用于每个轴。得到的算法是O(n^2)的空间和时间复杂度，其中n是您要搜索的二维空间的宽度和高度。
提醒一下，使用箱式函数进行一维卷积可以在O(n)的时间和空间内完成，并且可以原地完成。让x(t)为t=1..n的输入，y(t)为输出。对于t<1和t>n，定义x(t)=0和y(t)=0。将核f(t)定义为0之外的1，0..d-1为1。卷积的定义给出了以下公式：
y(t) = sum i x(t-i) * f(i) = sum i=0..d-1 x(t-i)
看起来这需要O(n*d)的时间，但我们可以将其重写为递归：
y(t) = y(t-1) + x(t) - x(t-d)
这表明一维卷积是O(n)的，与d无关。要执行二维卷积，只需为每个轴执行一维卷积。这有效是因为箱式核可以分解：通常，大多数核无法分解。高斯核是另一个可以分解的核，这就是图像编辑程序中高斯模糊如此快的原因。
对于您指定的数字类型，这将非常快速。500x500是一个极小的数据集，您的计算机最多可以在几毫秒内检查202,500个区域。您必须问自己是否值得花费额外的时间来进一步优化，可能需要几小时、几天或几周。
这与justhalf的解决方案相同，但由于分解的卷积，区域大小不会影响算法的速度。
假设至少有一个点。不失一般性，考虑2D空间为整个平面。让d为区域的宽度和高度。令N为点的数量。
引理：存在具有其左边缘上的点的最大密度区域。
证明：假设R是最大密度区域。令R'为相同的区域，向右平移R左边缘和R中最左边点之间的距离。所有在R中的点也必须在R'中，因此R'也是最大密度区域。将所有点插入K-D树中。这可以在O(N log2 N)时间内完成。
对于每个点，考虑宽度为d，高度为2d的区域，在该区域上以点为中心在左侧边缘。称此区域为R。
查询区域R中的点集合S。这可以在O(N1/2+|S|)时间内完成。
找到包含S中最多点的d x d子区域。通过按y坐标排序S，然后执行线性扫描，可以在O(|S| log |S|)时间内完成。
得到的算法的时间复杂度为O(N3/2 + N |S| log |S|)。
当密度很高时，算法#1优于算法#2。只有当粒子密度非常低且总棋盘大小增加时算法#2才优于算法#1，此时算法#2优于算法#1的密度下降。
请注意，连续情况可以视为具有零密度，在这种情况下只有算法#2适用。
O(n^2 d^2)，在O(n^2)时间内迭代每个区域，然后在O(d^2)时间内计算该区域中的粒子数量，其中d是您区域的大小。O(n^2 + k*d^2)，其中
n是整个区域的大小（边长）k是粒子数d是每个区域的大小（边长）O(d^2)区域的计数O(n^2)区域，找到最大值using namespace std;
int mat [1024 + 3] [1024 + 3]; // Here n is assumed to be 1024
int main ()
{
int testCases; scanf ("%d", &testCases);
while ( testCases-- ) {
Set(mat, 0);
int d; scanf ("%d", &d); // d is the size of the region
int k; scanf ("%d", &k); // k is the number of particles
int x, y, cost;
for ( int i = 0; i < k; i++ ) {
scanf ("%d %d %d", &x, &y, &cost); // Read each particle position
// Update the count of the d^2 region affected by this particle
for ( int j = max (0, x - d); j <= min (x + d, 1024); j++ ) {
for ( int k = max (0, y - d); k <= min (y + d, 1024); k++ ) mat [j] [k] += cost;
}
}
int resX, resY, maxi = -1;
// Find the maximum count over all regions
for ( int i = 0; i < 1025; i++ ) {
for ( int j = 0; j < 1025; j++ ) {
if ( maxi < mat [i] [j] ) {
maxi = mat [i] [j];
resX = i;
resY = j;
}
}
}
printf ("%d %d %d\n", resX, resY, maxi);
}
return 0;
}
O(N^2 + K*D^2)，其中K是粒子数（在您的情况下为100），D是区域大小（在您的情况下为50），如此 C++ 代码所示：http://tausiq.wordpress.com/2012/08/24/uva-10360-rat-attack/。 - justhalf