从袋子中提取的高效时间算法

Question

你和你的朋友成功抢劫了一家装满钻石戒指的珠宝店。现在，你们想把你们的战利品分配给你们，但你们俩都有点贪心。你们俩都决定在分发戒指的时候试试运气。你的包里有N个戒指。你们两个决定一个接一个地轮流挑选一些戒指，直到袋子里一个都没有了。既然你是这个计划的策划者，你将采取第一轮行动。规矩是这样的-

1. 从包里拿出一枚戒指。

1. 拿走了一半可用的戒指。只有当袋子中的环数为偶数时，才能适用此规则。

两名抢劫犯都会尽量增加他们拥有的戒指的数量。如果你和对手都发挥得最好的话，找出在分配结束时你能得到的最大的环数。

输入

第一行包含一个整数N(1≤N≤1000000)，表示袋子中的环数。

输出

你能得到的戒指的最大数量。

样本输入

6

样本输出4

在这个问题上，任何人都会帮助我，任何语言都能工作，最好是Python。

Answer 1

这是一个O(logn)解决方案。让我们称f(n)为解决方案

很容易查证：

- if (n odd) f(n) = n - f(n-1)
- if (n even) f(n) = max(n - f(n-1), n - f(n/2))

说明:在n中，唯一的可能就是选择一个环，如果n是偶数，我们可以选择，选择一个或一半的数据包。

这些关系允许一个简单的迭代解，O(n)复杂度。

但是，通过注意以下问题，可以获得复杂度为O(logn)的递归解决方案：

如果，

• ，n == 4k+2，->，最好拿掉一半的戒指。在下一步中，如果

->最好只选择一个环，则另一个环只能选择一个环。然后，另一个只能接受其中一个，然后，我们到达前面的有利情况。

这里有一个简单的代码来说明这个算法。

比较了O(n)迭代解和O(logn)递归解的结果。

#include <iostream>
#include <algorithm>
#include <vector>

//  Iterative O(n) solution
int rings_iterative (int n) {
    std::vector<int> f (n+1);
    f[0] = 0;
    for (int i = 1; i <= n; ++i) {
        if (i%2) {
            f[i] = i - f[i-1];
        } else {
            f[i] = std::max(i - f[i/2], i - f[i-1]);
        }
    }
    return f[n];
}

//  Recursive O(logn) solution
int rings_recursive (int n) {
    //std::cout << "n = " << n << std::endl;
    if (n == 0) return 0;
    if (n%2) return n - rings_recursive (n-1);
    if (((n/2) % 2) || (n <= 4)) {      // n = 4k+2 -> divide by 2
        return n - rings_recursive(n/2);
    } else {                // n = 4k -> take one ring only
        return 1 + rings_recursive(n-2);
    }
    return -1;
}

int main () {
    int n = 999876;
    int ring1, ring2;
    ring1 = rings_iterative (n);
    ring2 = rings_recursive (n);
    
    std::cout << "n = " << n << " -> " << ring1 << " and " << ring2 << std::endl;
        
    int n_min = 643831;
    int n_max = 653875; 
    for (n = n_min; n <= n_max; ++n) {
        ring1 = rings_iterative (n);
        ring2 = rings_recursive (n);
        if (ring1 != ring2) {
            std::cout << "n = " << n << " -> " << ring1 << " and " << ring2 << std::endl;
            return 1;
        }
    }
    std::cout << "No difference\n";
    return 0;
}