2

一排有二十五个吧台凳。进入酒吧的顾客遵循以下两条规则：

  1. 顾客总是坐在离任何其他顾客最远的座位上。
  2. 一个客户永远不会坐在另一个客户旁边。

使用这两个规则，您应该将第一个顾客放在哪里，以便最大数量的顾客可以坐在吧台上？

我可以在 25 次大便的情况下解决它。但我想不出 n 个凳子的通用算法。

4

3 回答 3

5

听起来，这几乎与兰德尔·门罗 (Randall Munroe) 撰写的出色分析的国际小便池选择协议(ICUP) 完全相同，包括封闭式方程和最佳小便池计数图。在阅读此答案的其余部分之前，您应该阅读他的文章。

兰德尔在帖子中提到：

[我]如果你进入一间浴室，一排空置的小便池数量令人尴尬，而不是选择一个末端的小便池，你可以走三分之一的路。这会将尴尬的行分成两个最佳行，将最坏的情况变成最好的情况。

虽然他没有比这更详细，但它暗示了我们正在尝试做的事情。如果我们的小便池（或凳子，在我们的例子中）的数量令人尴尬，我们可以尝试让第一个人坐在座位上，这样他们就成为两个不同的最佳子组的末尾。

对于 7 个席位，基本的选择行为可以解决这个问题：

1 _ _ 3 _ _ 2

留下四个空位。但是，如果我们将第一个人安置在位置 3，我们将获得最佳的 3 和 5 子组，从而将我们的可能乘员增加一个。

3 _ 1 _ 4 _ 2

对于 25，基本行为同样是次优的，导致 9/25 的入住率在尴尬之前：

1 _ _ 6 _ _ 4 _ _ 7 _ _ 3 _ _ 8 _ _ 5 _ _ 9 _ _ 2

但是我们可以让某人坐在第 9 位，创建最佳的 9 17 个子组，如下所示：

3 _ 8 _ 5 _ 9 _ 1 _ 10 _ 6 _ 11 _ 4 _ 12 _ 7 _ 13 _ 2

导致最佳的 13/25 入住率。

更一般地说，我相信找到小于座位数的最大最佳数量，并让第一个人坐在那里（在 25 人的情况下，即 17 人，相当于从另一个方向算起的第 9 人）将始终最大化可占用椅子的数量。在最坏的情况下，比如 25，这相当于ceil(n/3)Randall 提到的。

在平均情况下（使用基本座位行为既不是最好的也不是最差的），我们不能总是通过只安排第一个人就座来达到 50% 的占用率，因为我们只能创建一个最佳子组，而将另一个子组留在不太理想的位置。因此，我们采用最大的最优子组以最小化次优座位的数量。例如，对于 20 个座位，我们取 17 个并创建一个 17 4 组，这样可以优化尽可能多的座位，只留下两个连续空的座位：

2 _ 7 _ 4 _ 8 _ 3 _ 9 _ 5 _ 10 _ 1 _ _ 6

这四组实际上在技术上既是最好的情况也是最坏的情况，但希望你能看到这种模式将如何扩展。

于 2012-09-24T20:13:57.317 回答
1

当你实际画图的时候，你会发现答案会很简单。例如，在以下情况下，您可以轻松地从左侧或右侧或中间选择座位。

Eg1 OOO---XOX--1

eg2 OOOOO--XOOOX--XOXOX--从3分解为1

Eg3 OOOOOOOOO--XOOOOOOOX--XOOOXOOOX--XOXOXOXOX--从7分解到3到1。

从这些例子中，我们可以做出如下陈述： 假设我们在两个选定的座位之间有一个空闲座位范围，当这些空闲座位的数量 N = 2^n-1 时，我们可以得到最大的座位选择范围。

证明：

  1. 基本情况：当n=1时，N=1，即XOX满足要求。
  2. 假设当 n <= k(with k>1) 时为真，这意味着当 2 个选定座位之间的空闲座位数为 N = 2^k-1 时，我们可以达到最大选择。对于 k+1 的情况，我们将有 N=2^(k+1)-1。然后我们可以在这个范围内选择中间的座位，把空闲的座位分成2段，每段的个数N' = (N-1)/2 = (2^(k+1)-1-1)/2 =2^k-1，从我们的假设来看是正确的。

所以这个问题的算法是：

给定座位数N，求2^n-1 < N-3的最大个数，然后测试N-1-(2^n-1)-1-1是否是2^m-1的形式.

在N=25的情况下，我们可以发现15是25以下的最大数，形式为2^4-1。由于 25-1-15-1-1 = 7 女巫是 2^3-1 的形式。所以25个座位可以达到最大选择。根据我们的分析，我们可以在 17 点或 9 点选择第一个座位。

于 2015-02-12T22:10:50.327 回答
0

以下是我的分析。

为了争论起见，假设第一个人坐在中间的某个地方，不要太靠近两端。这将给我们一个像这样的模式，其中 x 表示占用座位，_ 表示空闲座位：

_ _ _ ... _ x _ ... _ _ _

第一个坐在这个人左边的顾客将坐在最左边。同样，第一个坐在此人右侧的顾客将坐在最右端。这给我们留下了这样的模式，其中 -m- 表示 m 个连续的空闲座位：

x _ -m- _ x _ -n- _ x

将此称为“基本配置”，座位总数为 s = m + n + 7。

好的，现在我们的问题被分成大小为 m 和 n 的两个子问题，每个子问题都将由坐在尽可能靠近每个区域中间的客户来填充。

对于最大的最终入住率，我们希望 m 和 n 是“理想”数字，定义如下：

a is ideal if a = 2b + 3 and b is ideal  (i.e., we will get -b- _ x _ -b-).

这里的想法是，理想数量的座位可以通过（1）占据 a 的中间座位和（2）递归求解大小为 b 的两个子问题来最大程度地占据。

最不理想的数是 1。

由此，我们可以建立前几个理想数字：

1, 5, 13, 29, ...

现在，对于 s = 25，我们的基本配置是 25 = m + n + 7，我们希望 m 和 n 是理想的。嗯，25 - 7 = 18 和 18 = 5 + 13，这是理想的！

因此，对于 25 个座位​​，我们将第一个人坐在 4 + 5 = 9 或 4 + 13 = 17 的座位上，并且我们保证以最大占用率结束。

在我们结束之前要检查的最后一件事：如果第一位顾客坐在凳子上怎么办？然后，在第二个客户坐下后，我们将

x _ -m- _ x

其中 m 必须是一个理想的数字。对于 25 个座位​​，这给出了 25 - 4 = m = 21，这并不理想。因此，第一位顾客不能坐在任何一端，最多可容纳 25 个座位​​。

呸呸呸呸！

于 2012-09-27T03:02:09.090 回答