algorithm - 在 O(1) 中高效地计算序列 2、2、4、2、4、6、2、4、6、8 ... 的第 i 个元素

Question

所以这个问题给出了一些输入的以下输出:

2, 2, 4, 2, 4, 6, 2, 4, 6, 8, 2, 4, 6, 8, 10, ... 用于输入

n = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...

第一个最初的想法当然是使用 DP 来存储答案直到输入的约束 (n = 500000) 并且只从已经生成的数组中检索答案。

然而，看到上面的数字让我认为这可能是一个可以使用一些数学公式(通常是O(1))来回答的序列，因此不必求助于 DP (它需要 O(n) 来生成，但是 O(1) 来检索。有没有一种方法可以制定一个公式来获取 的值>i - i 是用户输入的第一个元素？

Answer 1

我们可以将上面的序列操作成一组序列，即:

2, 2, 4, 2, 4, 6, 2, 4, 6, 8, ...

进入

1, 2, 3, 4, ... 此序列中的每个数字表示其组中成员的数量。

这里的想法是将第 i 元素归类到一个组中。一旦我们找到它的组，我们就可以从 i 中减去前一组的数量元素，从而得到它的精确位置 position相对于它自己的组(例如上面序列中的第二个 4 是第三组的第二个元素)。我们知道元素的位置决定了它的值，也就是我们只需要将它的位置乘以2。这意味着如果我们能得到它在它的组中的相对位置，我们就能找到它的值。

例如，上面序列中的第一个6。它在组 3 内，相对位置 3，值为 6。给定它在第一个序列中的位置(即位置 6)，我们如何计算它的值？我们可以在second序列上使用等差数列公式(因为它是算术)来近似计算公式上的n Sn = n/2 * (2a + (n-1))。求出n值后，如果不是整数，我们就知道n不可能是四舍五入后的值.

计算上面序列中的第一个 6 以找到它的组:

Sn = n/2 * (2a + (n-1))
6 * 2 = n * (2 + n - 1)
12 = n^2 + n
0 = n^2 + n - 12

从那里，我们可以使用 quadratic formula 计算positive n ，即 n = (-b+sqrt(b^2-4ac)/2a)。

n = [-1 + sqrt(1-4*1*-22)]/2
n = [-1 + sqrt(89)]/2
n = 2.9278273

我们将此 n 取整为 3，现在我们知道第一个 6 属于 3 组。要找到它在其组中的相对位置，我们可以简单地从 i 中减去前面组中的元素数量。要找到前面组中元素的数量，我们可以使用相同的算术序列公式，尽管 n 为 3 - 1(因为我们正在计算成员的数量在前一组)。

S2 = 2/2 * (2 + 2 - 1)
S2 = 3

知道第 i 元素之前有 3 个成员，我们可以从 i (6) 中减去 3 得到 3 (它在其组中的相对位置)。然后，我们可以找到它的值乘以 2 得到 6。

C++ 代码:

int main() {
    int n;
    double approximateN;
    int S_approximateNMinusOne;

    cin >> n;
    approximateN = ceil((sqrt(1 + 4 * n * 2) - 1.00) / 2.00);
    S_approximateNMinusOne = (approximateN - 1) * (2 + approximateN - 2) / 2.00;
    cout << (n - S_approximateNMinusOne) * 2 << endl;

    return 0;
}