这道题的意思紫书上是错误的……

难怪一开始我非常奇怪为什么第二个样例输出的是2， 按照紫书上的意思应该是22

然后就不管了，先写， 然后就WA了。

然后看了https://blog.csdn.net/wcr1996/article/details/43774331

发现是题意是错误的。

是从1到n的排列变成给的排列， 而不是反过来

其他人的博客都是

逆向思维来写， 也就是我原来写误打误撞的那样， 只不过操作反过来， 以及最后

输出是反的。

这种方法很值得学习

其实正向也不难， 无非是设置了一种新的优先级

把原来1至n的排列看作乱序的， 把给的排列看作有序的， 只需要给每个值分配一个id就好了。

然后我惊奇地发现， 直接正向来写最后输出的答案和给的输出样例是一模一样的。

可能出题者就是正向来写的。

我的解题思路就是一开始“忽略”交换需要在头举行， 先搜一遍然后搜到不是升序的时候， 就直接交换这两个元素

在交换的时候放到头在交换。实际上就是把序列中不是升序的交换过来， 然后一直这么做， 直到全部为升序为止。

然而需要在头进行只是一个“副产品”。具体看代码。

#include
    
     #include
     
      #include
      
       #include
       
        #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 312;int id[MAXN], n;deque
        
          q;vector
         
           ans;void Swap(int cur){ REP(i, 0, cur) { q.push_back(q.front()); q.pop_front(); ans.push_back(2); } ans.push_back(1); swap(q[0], q[1]);}bool check(){ REP(i, 0, n) { if(id[q[i]] > id[q[(i+1)%n]] && !(id[q[i]] == n && id[q[(i+1)%n]] == 1)) { Swap(i); return true; } } return false;}int main(){ while(~scanf("%d", &n) && n) { ans.clear(); while(!q.empty()) q.pop_back(); int start, x; REP(i, 1, n + 1) { scanf("%d", &x); id[x] = i; q.push_back(i); } while(check()); if(id[q[0]] != 1) { for(start = 0; id[q[start]] != 1; start++); REP(i, 0, start) ans.push_back(2); } REP(i, 0, ans.size()) printf("%d", ans[i]); puts(""); } return 0;}