c - SPOJ - 好斗的奶牛， "largest minimum distance"术语的含义是什么？

Question

我正在尝试理解 AGGRCOW - Aggressive cows 的问题在斯波伊。但这个输出是怎么来的，我不明白。首先我想也许它们之间的距离就像这个输入一样:

Input:
5 3 
1 2 4 8 9

Ouput: 3

首先我们将cow1放入位置arr[0]，然后将cow2放入arr[2]。我们不将cow2放入arr 1因为这样他们之间就没有距离了(2-1=1)。现在cow2和cow1的距离是3个单位。因此我们将cow2放入arr[2]中。最后我们把cow3放在arr[3]中，因为cow3和cow2之间的距离是4。然后我们比较这个3<4。输出 3。

但是当我尝试对此输入应用相同的逻辑时:

Input:
6 3 
2 3 4 5 8 9

Ouput: 3

按照我的逻辑，它应该是2。就好像我们将cow1保留在arr[0]中，将cow2保留在arr[2]中，那么距离是4-2=2。而且是最小的。但是当我想通过谷歌搜索查看实际值应该是多少时，我发现它是3。我不明白它怎么是3。为什么不是2？我只想要这个问题的解释，而不是代码。

Answer 1

问题是您有 N 个摊位位置，a₀ 到 a_{< i>N-1}。您必须填写其中的 C 个，但填​​充的摊位编号之间的间隔应尽可能大。输出是所有已满的隔间所实现的分离。也就是说，如果您输出 3，则意味着您的解决方案表示“我可以填充这些隔间，以便任何两个填充的隔间之间的距离至少为 3”。。

如果你仔细想想，你实际上是在寻找任何两个已满的摊位之间的最小距离，并且你正在尝试最大化它，而不影响到任何其他已满的摊位的距离。因此:最大最小距离。

输入的形式

N C
a₀ a₁ ... a_N-2 a_N-1

第二个例子是

6 3 
2 3 4 5 8 9

这意味着有 6 个摊位:2、3、4、5、8 和 9，其中三个需要填充，保持摊位编号之间的最大间隔。

最佳解决方案是使用档位 2、5 和 9。此时间隔为 5-2 = 3 和 9-5 = 4，结果是其中最小的 3。