#c++#：沃瑟夫问题，指导指导

Question

沃瑟夫问题：约瑟夫问题的变体

#include <bits/stdc++.h>
using namespace std;

const int size = 5001;

int n, front = 1, rear = size;
int q[size + 1];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        rear = rear % size + 1;
        q[rear] = i;
    }
    int x = 0, i = 1;
    while (rear % size + 1 != front) {
        int y = q[front];
        front = front % size + 1;
        x++;
        if (x == i * i) {
            printf("%d ", y);
            x = 0;
            i++;
        } else {
            rear = rear % size + 1;
            q[rear] = y;
        }
    }
    return 0;
}

因为n 最大是5000，一个for，一个while会超时间复杂度（1s）
希望帮助改良代码

Answer 1

【以下回答由 GPT 生成】

这段代码中有两个循环会导致超时问题，一个是for循环，一个是while循环。下面是对代码的改进建议：

1. 使用std::queue代替数组：当前代码使用数组来模拟队列，但是使用动态数组会导致较慢的性能。C++标准库中的std::queue提供了队列数据结构，并且封装了实现细节，可以提供更高效的队列操作。因此，建议使用std::queue代替数组实现队列。

2. 避免使用std::endl：当前代码在输出时使用了printf配合std::endl来刷新输出缓冲区。然而，std::endl会在遇到换行符时强制刷新输出缓冲区，在循环中频繁使用会导致性能下降。替代方案是使用换行符"\n"来换行，然后使用std::flush手动刷新输出缓冲区。

下面是根据上述建议改进后的代码：

#include <iostream>
#include <queue>
#include <cmath>

int main() {
    int n;
    std::cin >> n;

    std::queue<int> q;
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }

    int x = 0, i = 1;
    while (!q.empty()) {
        int y = q.front();
        q.pop();
        x++;
        if (x == i * i) {
            std::cout << y << " ";
            x = 0;
            i++;
        } else {
            q.push(y);
        }
    }

    std::cout << std::flush;

    return 0;
}

以上是改进后的代码，通过使用std::queue来代替数组实现队列，并在输出时使用换行符"\n"来换行，然后使用std::flush手动刷新输出缓冲区，可以有效提高代码的性能。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^