【习题 8-6 UVA

在这里输入题意

【题解】

想把数字i从位置j移动到位置i 可以这样。假设mov(x,y)表示将(x..x+len/2-1)和(x+len/2..y)交换。则可以先进行mov(j,i-1)操作。 (如果(j,i-1)的长度为奇数,终点就变为i-2) 令len = (i-1)-j+1 //当然长度为奇数的时候就是(i-2)-j+1了 x = j+len/2 =>x就是数字i新的位置然后令len2 = i-x; 然后再进行一次mov(x-len2+1,i)操作就可以了。这样x就能到达i所在的位置了。且不会影响到i+1..n这些数字(它们已经用同样的规则放好到了原位置,即是i是逆序归位的之所以要先进行一次mov(j,i-1)操作.是为了能让那个x-len2+1尽可能地大。不让它小于1，因为<1就不合法了。而我们让上界为i-1 就可以保证这个x-len2+1>=1了 (因为i相当于从左半边翻转到右半边了,那么i的左半部分肯定有len2个数字的。 (暴力翻转并没有超时呀 (每个数字只会做两次,所以最多只会有20000次操作

【代码】

/*
  	1.Shoud it use long long ?
  	2.Have you ever test several sample(at least therr) yourself?
  	3.Can you promise that the solution is right? At least,the main ideal
  	4.use the puts("") or putchar() or printf and such things?
  	5.init the used array or any value?
  	6.use error MAX_VALUE?
  	7.use scanf instead of cin/cout?
  	8.whatch out the detail input require
*/
/*
    一定在这里写完思路再敲代码!!!
*/
#include <bits/stdc++.h>
#define index fuck_index
using namespace std;

const int N =  1e4;

int n,a[N+10],index[N+10];
vector<pair<int,int> > v;

void fanzhuan(int l,int r){
    if (l==r) return;
    v.push_back({l,r});
    int len = r-l+1;
    int mid = l+len/2-1;
    for (int i = l;i <= mid;i++){
        swap(a[i],a[i+len/2]);
        index[a[i]] = i;
        index[a[i+len/2]] = i+len/2;
    }
}

int main(){
	#ifdef LOCAL_DEFINE
	    freopen("rush_in.txt", "r", stdin);
	#endif
	ios::sync_with_stdio(0),cin.tie(0);
    int T;
    cin >> T;
    while (T--){
        v.clear();
        cin >> n;
        for (int i = 1;i <= n;i++) cin >> a[i],index[a[i]] = i;
        for (int i = n;i >= 2;i--){
            int x = index[i],y = i;
            if (x==y) continue;
            if (x>y) swap(x,y);
            int ty = y-1;

            int len = ty-x+1;
            if (x!=ty){
                if ((len)&1) ty--,len--;
                if (x!=ty)fanzhuan(x,ty);
            }

            x = x+len/2;
            len = y-x;
            x = x - len+1;
            fanzhuan(x,y);
        }
        cout <<(int) v.size()<<endl;
        for (auto temp:v){
            cout <<temp.first<<' '<<temp.second<<endl;
        }
    }
	return 0;
}