UVA 11925 Generating Permutations 生成排列（序列）

题意：要用一个有序的序列生成给定序列，操作有两种，一是交换前两个元素，二是把第一个元素移动到最后去。

思路有两种：

1.映射，把给定序列映射成有序的序列，然后按照同样的替换规则把有序的序列映射掉，然后就可以排序啦。

具体解释可以看SRM 664的C题

2.逆向思考，把给定序列变成有序，操作相应变化一下，最后逆序输出操作。

至于排序的问题，把序列看成一个环，第二种操作相当改变了可交换元素的位置，然后就可以等效为冒泡排序啦。。。

第二种思路需要注意的一点是，是因为是环状的，和冒泡排序有所区别，最大的元素在头部的时候不能进行交换了，否则陷入死循环，最大的元素所在的位置相当与链状时候的最后面的有序区，是不需要比较的。

冒泡排序一次交换恰好消除一个逆序对，因此判断终止可以先求出逆序对总数，交换一次逆序数减一

#include<bits/stdc++.h>

using namespace std;

int a[],t[],inv;

void merge_sort(int l,int r)

{

    if(l == r) return;

    int mid = (l+r) >> ;

    merge_sort(l,mid);

    merge_sort(mid+,r);

    int p = l, q = r, k = l;

    while(p <= mid && q <= r){

        if(a[p]>a[q]) {

            inv += mid - p + ;

            t[k++] = a[q++];

        } else {

            t[k++] = a[p++];

        }

    }

    if(p>mid) for(int i = q; i <= r; i++) t[k++] = a[i];

    else for(int i = p; i <= mid; i++) t[k++] = a[i];

    for(k = l; k <= r; k++) a[k] = t[k];

}

int main()

{

    //freopen("in.txt","r",stdin);

    int n, b[];

    while(scanf("%d",&n),n){

        for(int i = ; i < n; i++) {

            int t; scanf("%d",&t);

            b[t-] = i;

        }

        memcpy(a,b,sizeof(int)*n);

        inv = ;

        merge_sort(,n-);

        for(int i = n-; i >=  && inv ; i--){

            for(int j = ; j < i; j++){

                if( b[j] > b[j+]) {

                    swap(b[j],b[j+]);

                    putchar('');

                    inv--;

                }

                putchar('');

            }

            //continue move i -> 1

            for(int j = i; j < n ;j++){

                putchar('');

            }

        }

        putchar('\n');

    }

    return ;

}

巴特西

UVA 11925 Generating Permutations 生成排列（序列）

最新文章

热门文章

巴特西

UVA 11925 Generating Permutations 生成排列 （序列）

最新文章

热门文章

UVA 11925 Generating Permutations 生成排列（序列）