这道题的意思紫书上是错误的……
难怪一开始我非常奇怪为什么第二个样例输出的是2， 按照紫书上的意思应该是22
然后就不管了，先写， 然后就WA了。
然后看了https://blog.csdn.net/wcr1996/article/details/43774331
发现是题意是错误的。
是从1到n的排列变成给的排列， 而不是反过来
其他人的博客都是逆向思维来写， 也就是我原来写误打误撞的那样， 只不过操作反过来， 以及最后
输出是反的。这种方法很值得学习
其实正向也不难， 无非是设置了一种新的优先级
把原来1至n的排列看作乱序的， 把给的排列看作有序的， 只需要给每个值分配一个id就好了。
然后我惊奇地发现， 直接正向来写最后输出的答案和给的输出样例是一模一样的。
可能出题者就是正向来写的。
我的解题思路就是一开始“忽略”交换需要在头举行， 先搜一遍然后搜到不是升序的时候， 就直接交换这两个元素
在交换的时候放到头在交换。实际上就是把序列中不是升序的交换过来， 然后一直这么做， 直到全部为升序为止。
然而需要在头进行只是一个“副产品”。具体看代码。
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
const int MAXN = 312;
int id[MAXN], n;
deque<int> q;
vector<int> 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;
}