gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-30 14:44:47 24 4
gpt4 key购买 nike

我正在尝试理解 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?我只想要这个问题的解释,而不是代码。

最佳答案

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

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

输入的形式

N C
a0 a1 ... aN-2 aN-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。

关于c - SPOJ - 好斗的奶牛, "largest minimum distance"术语的含义是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53391955/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com