【习题 8-6 UVA - 1611】 Crane

在这里输入题意

【题解】

想把数字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相当于从左半边翻转到右半边了,那么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;

}

巴特西

【习题 8-6 UVA - 1611】 Crane

最新文章

热门文章