习题8-6(uva-1611)

1.冒泡,依次选1-n
2.先把当前选择的数 放在前半部分(保证下一步能把当前数放在前面)
每个数最多2个操作

#include <iostream>
#include <istream>
#include <sstream>
#include <vector>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <chrono>
#include <ctime>
#include <cmath>
#include <cctype>
#include <string>
#include <cstdio>
#include <iomanip>#include <thread>
#include <mutex>
#include <condition_variable>
#include <functional>
#include <iterator>
using namespace std;
const int maxn = 1e5 + 7;
int input[maxn],n,ans[maxn<<1],cnt;void SwapArr(int first, int last) {
    if (first >= last) return;int* fp = input + first, * lp = input + (first + last >> 1) + 1,*over = lp;while (fp != over) {
    swap(*fp++, *lp++);}ans[cnt++] = first;ans[cnt++] = last;
}
void GetResult(int first, int last) {
    while (first <= last && input[first] == first) ++first;if (first > last) return;int index = find(input + first, input + last + 1,first) - input,len = index - first;if (index > (first + last >> 1)) {
    int tcnt = index - first + 1,tFirst = first;if (tcnt & 1) tFirst++;SwapArr(tFirst, index);len = find(input + first, input + last + 1, first) - input;len -= first;}SwapArr(first, first + len * 2 - 1);GetResult(first + 1, last);
}int main()
{
    int t;cin >> t;while (t--) {
    cin >> n, cnt = 0;for (int i = 1; i <= n; i++)cin >> input[i];GetResult(1, n);cout << (cnt >> 1) << endl;for (int i = 0; i < cnt; i+=2) {
    cout << ans[i] << " " << ans[i + 1] << endl;}}return 0;
}