ACGO首个AC作者的题解（我真的太棒了）（首个AC题解）

<本题解参考洛谷的第一个题解>

洛谷传送门

---

正片开始了！

这道题用到的知识点既然是是模拟，那么就用模拟来做

题目：

zky有n张扑克，编号从1到n，zky 把它排成一个序列，每次把最上方的扑克牌放在牌堆底，然后把下一张扑克牌拿出来输出，最终输出的序列恰好是从1到n，faebdc 问你原序列是什么。

分析思路：

有点像约瑟夫问题的逆推，可以先定义一个单向队列，初始化为1到n，逆推来确定位置（每个数字代表位置）.

举个栗子：

比如说n=5，那么队列初始化为{1,2,3,4,5}，进行逆推，现将1取出再加入队列，得到{2,3,4,5,1}，那么第一个数字的位置就在索引为2的地方（记得pop()），重复步骤:

次数	得到队列	位置
0	1,2,3,4,5	\
1	2,3,4,5,1	2
2	4,5,1,3（2被pop()了）	4
3	1,3,5（4被pop()了）	1
4	5,3（1被pop()了）	5
5	3（5被pop()了）	3

最终得到 1,2,3,4,5 的位置分别为 2,4,1,5,3, 得到答案 3,1,5,2,4

那么，根据这种方法，就可以求解了，时间复杂度 $O(n)$

答案如下：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    queue<int> q; //定义单向队列
    for(int i = 1;i <= n;i++) q.push(i); //初始化为1到n
    int wz[n + 5]; //确定位置
    for(int i = 1;!q.empty();i++){
        //进行逆推，确定位置
        q.push(q.front());
        q.pop();
        wz[i] = q.front();
        q.pop();
    }
    int a[n + 5];
    //获取答案
    for(int i = 1;i <= n;i++){
        a[wz[i]] = i;
    }
    //输出答案
    for(int i = 1;i <= n;i++){
        cout << a[i] << " ";
    }
    return 0;
}

---

单向队列基本常用操作：

函数	栗子	效果
queue<数据类型> 队列名	queue<int> a	定义名叫 a 的 整型 队列
队列名.push(x)	a.push(1)	将1加入名叫a的队列中
队列名.pop()	a.pop()	删除a的队列的队首元素
队列名.front()	a.front()	获取名叫a的队列的队首元素
队列名.back()	a.back()	获取名叫a的队列的队尾元素
队列名.empty()	a.empty()	检测名叫a的队列是否为空，为空返回true，不为空返回false
队列名.size()	a.size()	获取名叫a的队列的元素个数（长度）