2

在约瑟夫斯问题中，我们有 n 个人，从 1 到 n 编号。每回合你跳过k个人并杀死下一个。通常你打印最后一个幸存者，我对受害者的顺序感兴趣。我尝试根据网上找到的建议使用循环链表来做到这一点。当输入像 n=123456 这样大时，我的算法仍然不够快；k=1000000000。我的时间目标是不到一秒。我认为时间复杂度是 O(nk)，因为所有链表操作都是 O(1)，并且对于每个人，我必须打印它们的值并可能移动 k 步。我是否应该找到一些不同的策略我是否缺少一些明显的优化技术？

#include <vector>
using namespace std;
 
struct Node {
    int value;
    struct Node* next;
};
 
Node* insertToEmpty(struct Node* last, int x) {
    Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->value = x;
    last = temp;
    last->next = last;
    return last;
}
 
Node* insert(struct Node* last, int x) {
    if (last == NULL) {
        return insertToEmpty(last, x);
    }
    Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->value = x;
    temp->next = last->next;
    last->next = temp;
    last = temp;
    return last;
}
 
Node* delete2(struct Node* prev, struct Node* current) {
    prev->next = current->next;
    return current->next;
}
 
int main() {
    int n;
    int k;
    cin >> n;
    cin >> k;
    if (n == 1) {
        cout << 1;
    }
    else {
        struct Node* curr;
        struct Node* prev;
        struct Node* last = NULL;
        for (int i = 1; i <= n; i++) {
            last = insert(last, i);
        }
        curr = last->next;
        prev = curr;
        for (int i = 1; i <= k%n; i++) {
            prev = curr;
            curr = curr->next;
        }
        do {
            cout << curr->value << " ";
            curr = delete2(prev, curr);
            n--;
            for (int j = 0; j < k%n; j++) {
                prev = curr;
                curr = curr->next;
            }
        } while (n > 1);
        cout << curr->value << endl;
 
    }
 
}
4

2 回答 2

1

使用简单的链表是正确的，O(nk)如果要加快速度，就必须使用更好的数据结构。我建议您使用跳过列表的变体来解决此问题。

跳过列表是一种二维结构。所有的值都在底层。每个级别只有一些值。它跳过了其他人。如果你想移动固定的步数，你可以向前和向上走，跳过元素，直到你可以向前和向下走到正确的位置。所有操作都是对数的。在你的情况下，这将使算法O(n (log(n) + log(k))

使用这种结构，节点将如下所示：

struct Node {
    int value;
    int count;
    struct Node* parent;
    struct Node* next;
    struct Node* first_child;
};

当您构建它时，您的底层将如下所示：

1 <-> 2 <-> 3 <-> ... <-> n

为first_child空，parent为指向下一级的指针，count为 1。

您的第二层将如下所示：

1 <-> 3 <-> 5 <-> ... <-> (n-1 or n as appropriate)

指向下一层中的first_child相同值，您parent指向上一层，并且count为2。

您的第三层将如下所示：

1 <-> 5 <-> 9 <-> 13 <-> ... <-> (something from n-3 to n)

指向下一层中的first_child相同值，您parent指向上一层，并且count为 4。

依此类推，直到您的最顶层仅包含1并且下一个值不在数组的末尾。会有O(log(n))层次。

好的，这就是设置。我们如何删除一些东西？我只会用我不知道的语言编写未经测试的代码，请原谅语法错误：

void remove (Node* node) {
    if (0 == --node->count) {
        /* Actually delete */
        if (node->prev != null) {
            node->prev->next = node->next;
        }
        if (node->next != null) {
            node->next.prev = node->prev;
        }
        if (node->parent != null && node = node->parent.first_child) {
            node->parent->first_child = node->next;
            node->parent->value = node->next->value;
        }
    }
    if (node->parent != null) {
        remove(node->parent);
    }
    if (0 == node->count) {
        free(node);
    }
}

此操作需要O(log(n))时间，因为那是有多少级别。

接下来，我们将需要一个小辅助函数来查找块中的最后一个节点。这意味着我们想要向下移动直到到达那个节点。

Node* last_in_block (Node* node) {
    if (node->next == null) {
        /* Slide down the end. */
        while (node->first_child != null) {
            node = node->first_child;
        }
    }
    else {
        while (node->first_child != null) {
            Node* child = node->first_child;
            while (child->next->parent == node) {
                child = child->next;
            }
            node = child;
        }
    }
    return node;
}

现在向前推进一些步骤呢？这有点棘手。

首先让我们同意，在特定地点意味着“我刚刚访问过这里并继续前进”。所以我们可以递归定义move为“寻找节点越过，然后从块中减去它的计数”。但是有一些边缘情况。再次未经测试的代码，但以下应该给出我的意思的一般概念。

Node* move (Node* node, int steps) {
    if (node->next == null) {
        /* We are at the end, go to the top */
        while (node->parent != null) {
            node = node->parent;
        }

        /* Go around the loop as many times as needed. */
        steps = steps % node->count;

        /* Travel down to the right level to continue our journey */
        while (steps < node->count) {
            node = node->first_child;
        }

        /* And step over this node */
        steps -= node->count;
    }

    if (steps <= 0) {
        /* EXIT HERE IF JOURNEY IS ENDED */
        return last_in_block(node);
    }

    /* Right now the following are true.

       1. We are not at the end.
       2. We are also not at the top level (because the node there is at the end).
       3. node->next is also not at the top level (because it is at our level).
       4. 0 < steps, so traveling down we will eventually find a doable step.
    */

    if (steps <= node->next->count) {
        /* travel forward, then down to the right level. */
        node = node->next;
        while (steps < node->count) {
            node = node->first_child;
        }
    }
    else if (node->parent != node->next->parent && node->next->parent->count < steps) {
        /* travel forward and then up */
        node = node->next;
        while (node->parent != null && node->parent->count < steps) {
            node = node->parent;
        }
    }
    else {
        /* just travel forward */
        node = node->next;
    }
    /* And now we step over the block represented by this node. */
    steps -= node->count;
    return move(node, steps);
}

现在有了这个数据结构，你可以弄清楚如何前进，移除你站立的位置，再次前进，等等。

于 2021-01-15T20:37:12.370 回答
0

k我们可以通过使用带有尺寸装饰的treap来获得独立。O(n log n).

样本输入、输出：

stdin:   10 5
stdout:  4 9 5 1 8 7 0 3 6

C++改编自Kimiyuki Onaka的代码：

#include <iostream>
#include <tuple>
#include <random>
#include <memory>

using namespace std;

template <typename T>
struct treap {
    typedef T value_type;
    typedef double key_type;
    value_type v;
    key_type k;
    shared_ptr<treap> l, r;
    size_t m_size;
    treap(value_type v)
            : v(v)
            , k(generate())
            , l()
            , r()
            , m_size(1) {
    }
    static shared_ptr<treap> update(shared_ptr<treap> const & t) {
        if (t) {
            t->m_size = 1 + size(t->l) + size(t->r);
        }
        return t;
    }
    static key_type generate() {
        static random_device device;
        static default_random_engine engine(device());
        static uniform_real_distribution<double> dist;
        return dist(engine);
    }
    static size_t size(shared_ptr<treap> const & t) {
        return t ? t->m_size : 0;
    }
    static shared_ptr<treap> merge(shared_ptr<treap> const & a, shared_ptr<treap> const & b) { // destructive
        if (not a) return b;
        if (not b) return a;
        if (a->k > b->k) {
            a->r = merge(a->r, b);
            return update(a);
        } else {
            b->l = merge(a, b->l);
            return update(b);
        }
    }
    static pair<shared_ptr<treap>, shared_ptr<treap> > split(shared_ptr<treap> const & t, size_t i) { // [0, i) [i, n), destructive
        if (not t) return { shared_ptr<treap>(), shared_ptr<treap>() };
        if (i <= size(t->l)) {
            shared_ptr<treap> u; tie(u, t->l) = split(t->l, i);
            return { u, update(t) };
        } else {
            shared_ptr<treap> u; tie(t->r, u) = split(t->r, i - size(t->l) - 1);
            return { update(t), u };
        }
    }
    static shared_ptr<treap> insert(shared_ptr<treap> const & t, size_t i, value_type v) { // destructive
        shared_ptr<treap> l, r; tie(l, r) = split(t, i);
        shared_ptr<treap> u = make_shared<treap>(v);
        return merge(merge(l, u), r);
    }
    static pair<shared_ptr<treap>,shared_ptr<treap> > erase(shared_ptr<treap> const & t, size_t i) { // (t \ t_i, t_t), destructive
        shared_ptr<treap> l, u, r;
        tie(l, r) = split(t, i+1);
        tie(l, u) = split(l, i);
        return { merge(l, r), u };
    }
};

typedef treap<int> T;
int main() {
    int n; cin >> n;
    int k; cin >> k;
    shared_ptr<T> t;
    for (int i=0; i<n; i++)
        t = T::insert(t, i, i);
    
    int size = n;
    int position = 0;
    for (int i=0; i<n-1; i++){
        position = (position - 1 + k) % size;
        size = size - 1;
        shared_ptr<T> u;
        tie(t, u) = T::erase(t, position);
        cout << u->v << " ";
    }
    cout << endl;
    return 0;
}
于 2021-01-16T16:33:34.203 回答