UVA - 1611 Crane 推理 ＋ 貪心

UVA - 1611 Crane 推理 ＋ 貪心

題目大意：輸入一個1-n的排列，要求經過操作將其變換成一個生序序列。操作的規則如下
每次操作時，可以選一個長度為偶數的連續區間，交換前一半和後一半
提示：2n次操作就足夠了

解題思路：這句提示是關鍵，2n次操作，表明每個數最多只需要兩次操作。
應該從左到右依次操作過去，先將前面的數安定好了，就可以不用管前面的數了
假設操作到第i個位置，而i這個數剛好在pos這個位置上，現在就要判斷一下能否直接將pos上的i經過操作調到i這個位置上
如果 i + (pos - i) * 2 - 1 <= n　就表示可以一次操作完成
在上面條件不成立的情況下，又分為兩種情況
一種是pos和i的距離是奇數的情況：那麼就直接將［i，pos］這個區間的值進行交換即可
另一種是距離為偶數的情況，那就把[i+1,pos]這個區間的值進行交換即可

參考了別人的代碼：

#include
#include
#include
#include
using namespace std;
typedef pair Pair;
#define maxn 10010
int num[maxn];

void change(int l, int r) {
    for(int i = l, j = l + (r - l + 1) / 2; j <= r; j++, i++)
        swap(num[i],num[j]);
}
int main() {
    int test, n;
    scanf("%d", &test);
    while(test--) {
        scanf("%d", &n);
        for(int i = 1 ; i <= n; i++)
            scanf("%d", &num[i]);
        vector > ans;
        for(int i = 1; i <= n; i++) {
            int pos;
            for(int j = i; j <= n; j++)
                if(num[j] == i) {
                    pos = j;
                    break;
                }
            if(pos == i)
                continue;
            if(i + 2 * (pos - i) - 1 <= n) {
                ans.push_back(Pair(i,i + 2 * (pos - i) - 1));
                change(i, i + 2 * (pos - i) - 1);
            }
            else {
                if((pos - i) % 2) {
                    ans.push_back(Pair(i, pos));
                    change(i,pos);
                }
                else {
                    ans.push_back(Pair(i + 1, pos));
                    change(i + 1, pos);
                }
                i--;
            }
        }
        cout << ans.size() << endl;
        for(int i = 0; i < ans.size(); i++)
            printf("%d %d\n",ans[i].first, ans[i].second);
    }
    return 0;
}