在 O(n) 时间内重新创建 m 个 1-n 之间非递增整数的数组，每个索引最多 ⌈log n⌉ 猜测以及对错误猜测的定向响应

Question

在游戏中，您的目标是猜测 1 到 n 范围内的数字。每轮最多允许进行 ⌈log n⌉ 次猜测。在 m 轮的过程中（其中 m < n), you record the correct answers in an array M[i], with i starting from 1 to m. Initially, designing an algorithm that runs in O(m*log(n)) time is straightforward. However, a new condition has been introduced: M[i] ≤ M[j] for all i > j，这意味着答案按降序排列。任务是找到一种在给定修改条件的情况下在 O(n) 时间内运行的算法。

基于条件 M[i] ≤ M[j]（对于所有 i > j），我可以将范围缩小到 1 到 n 之间。但在最坏的情况下，我仍然无法得到O(n)。 另外，你不能粗暴地强制猜测数字，这是有限制的。

一些澄清： 1.当你猜测时，系统会告诉你太大或太小。 （这是一个经典的二分搜索问题） 2.答案按降序排列。 3.每轮猜测次数的限制是⌈log n⌉，而不是log(n) + 1，抱歉我之前表述中的错误。

我举个例子，希望对你有帮助。

• 我们来玩一个游戏，你需要猜一个1到100之间的整数（n = 100）。
• 您需要玩 10 轮（m = 10）。
• 在每一轮中，您都有 ⌈log n⌉ 种猜测。我会告诉你你的答案是否太大或太小。
• 下一轮的答案总是等于或小于上一轮的答案。如：{98,88,76,76,76,74,65,43,43,42}

如果您需要更多信息，请告诉我。

提前致谢！

Answer 1

输入：

• n：整数
• M：1-n 范围内的整数非递增数组，其中 1 作为第一个索引。 |米| = 米 < n.

目标：通过对每个索引进行最多 ⌈log n⌉ 次猜测来按顺序重新创建 M，运行时间为 O(n)。 IE。我们不能直接访问 M，而只能猜测第一个未确定索引的值，并了解我们的猜测是否正确、太大或太小。

注释：

• 令 k = ⌈log n⌉，每个索引的最大猜测值。
• 设 M' 为输出数组。与输入数组不同，为了方便起见，这将是零索引的，其中 M'[0] = n。我们的目标是使 M'[i] = M[i] 为 1 <= i <= n.

给定 M[i-1] 确定 M[i] 的过程：

• 猜测 1：M[i-1] - k + 1
• 情况 1：如果我们的第一个猜测是正确的，那么我们就完成了。
• 情况 2：如果我们的第一个猜测太小，则正确答案是 M[i-1] 和 M[i-1] - k + 2（含）之间的 k-1 个值之一。我们将按降序猜测这些。
• 情况 3：如果我们的第一个猜测太大，则正确答案在 1 和 M[i-1] - k 之间（含）。我们使用二分搜索来确定最多 k-1 个额外步骤的正确答案，总共 k 个。

第一个约束分析： 最多猜测 k = ⌈log n⌉ 步中的每个数字。

案例1步骤：1

情况 2 步骤：M[i] - M[i-1] + 1 <= k

情况 3：二分查找最多需要 ⌈log n⌉ - 1 步，范围为 1 到 n - ⌈log n⌉。鉴于此，这最多需要 k 步（初始猜测，加上二分搜索最多 k-1 步）。

因此这满足了第一个约束，即每个数字最多可以通过 k 步来猜测。

第二个约束分析：算法应该是O(n)。

假设 G[i] 是我们为确定 M[i] 所做的猜测次数。请注意，对于所有三种情况，G[i] <= M[i-1] - M[i] + 1. In other words, if successive values of M differ by r, we will determine the latter value in at most r+1 guesses (never more than k, but we don't need that fact for this portion).

但是所有 M 的累积差异最多为 n-1，并且 |M| < n, so the total number of guesses must be <= (n-1) + |M| < (n-1) + n = 2n-1 = O(n).