这道题和例题8-1相当的像。
例题8-1https://blog.csdn.net/qq_34416123/article/details/80112017
一开始我还以为用归并的思想， 用交换把局部交换好， 然后再整体交换
花了一个一小时好不容易写好之后， 发现我这种解法局部有序并不能保证整体有序。
因为归并排序的局部是连续的， 是1 2 3 4 5这样的， 然后我这种方法局部排出来只能
1 3 5 6这样的， 所以最后合并不能保证整体有序……
然后
提示是2n次就够了。这个提示一开始没看懂啥意思， 然后后来突然想到， 这是不是
意味着每个数字最多两次操作就可以到该排到的位置？
然后又突然想到例题8-1， 那道题目也是翻转， 只不过翻转的方式不同而已。那道题的解法
是先翻到最顶上， 然后再翻下来。
类比一下这道题目， 是不是应该先翻到准备位置， 再翻到有序的时候应该在的位置。
然后我发现， 好像就是这样的， 只不过有的时候已经在准备位置了。
所以思路就是从1开始往后， 翻到数组中第0个位置， 第1个位置……（我是从0开始）
那么问题就在于到底怎么翻。
然后我发现， 可以求出当前这个数能往前翻的最前位置， 如果最前位置到的了目标位置， 那么就直接翻。
如果到不了， 那么就先翻一次， 位置移动到尽量前面， 然后第二次就一定能翻到目标位置了。
具体看代码
#include<cstdio>
#include<vector>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 11234;
int a[MAXN], n;
vector<pair<int, int> > ans;void Swap(int l, int r)
{ans.push_back(make_pair(l + 1, r));int len = (r - l) >> 1; REP(i, l, l + len) swap(a[i], a[i+len]);
}void move(int cur)
{int pos = 0, aim = cur - 1;while(a[pos] != cur) pos++;if(pos == aim) return;if(n - (n - pos) * 2 > aim) {if((n - aim) % 2 == 0) Swap(aim, n);else Swap(aim + 1, n);pos -= (n - aim) >> 1;}Swap(aim, aim + 2 * (pos - aim));
}int main()
{int T;scanf("%d", &T);while(T--){scanf("%d", &n);REP(i, 0, n) scanf("%d", &a[i]);ans.clear();REP(i, 1, n) move(i);printf("%d\n", ans.size());REP(i, 0, ans.size()) printf("%d %d\n", ans[i].first, ans[i].second);}return 0;
}