算法：圆盘盖米问题（圆的密铺？）

[caneman]

原问题为：

在一棋盘撒米，米粒落点不一，有口径大小不一的若干圆盘，问如何尽可能少的尝试，用圆盘覆盖尽可能多的米粒？（即：尽可能少的米粒裸露在外。）

条件：

1.黑盒系统，米粒位置信息均不可知。

2.仅当圆盘放下方可知其覆盖米粒数量，，每个圆盘覆盖的米粒不得超过 50 粒。

3.圆盘之间可以互相堆叠，已被下层圆盘覆盖的米粒不计入上层圆盘覆盖米粒的数量。

下面是我想到的一种解决方案，感觉还有很多地方可以优化，请问大伙有没有什么好的办法或者对这个算法的改进？

[necomancer]

所用的圆是大于这个四等分区间的，所以不存在漏掉粒子的问题。

[necomancer]

好像不是 O(Log(A))……算了，熬夜脑袋不太对。
或者第一步使用六方堆积，用 ~0.25 A 次尝试求出空间分布，再根据空间分布一次性解决问题？

[caneman]

@necomancer
盖上只能知道数量，这种一直往下迭代的方法是可行的，就是不知道这是不是最好的算法了。
如果问题再延申一下，如果上层的圆盘盖米数会计入下层圆盘覆盖的米粒数量呢？就是每个圆盘覆盖的米粒数是这个圆盘下所有的米粒数而不是 这个圆盘下未被其他下层圆盘覆盖过的米粒数。

[necomancer]

@caneman 没太理解，因为如果一个位置上叠加 1000 粒米，如果圆盘可以叠加，则需要 20 个。如果圆盘是上层会计入下层，那么无论怎么覆盖都覆盖不了啊，因为 1000 粒米在同一个位置，选多小的圆都会有交叠。

迭代法可能要考虑到最好和最差，我现在脑袋有点残，有时间我算一下。但是原则上六方堆积那个很好算，第一次使用大约 0.25A 次尝试求出粒子空间分布，第二次直接用大概 N/50 个圆进行覆盖。总尝试次数很稳定。当然，因为是保留用来探测粒子分布且覆盖小于 50 粒子的圆，总测试次数要很大程度上小过 0.25A + N/50 的，最差情况就是所有粒子堆叠，分布均匀应该会省力很多。

[adamwong]

不是图遍历吗就行吗，类似 n 个最大岛?