uva10570（枚举基准，贪心）

输入一个1至n的排列（n<=500），每次可以交换两个整数，用最小的交换次数把排列变成1至n的一个环状排列。

首先用\(O(n)\)的时间枚举一个排列，接着问题就转换为了用最少的交换次数将一个排列S变成有序的。

我们可以构造出一个置换E，表示S到1到n的升序排列的置换。如果把E写成若干个轮换连接起来的形式。不难发现两条规律：

要将一个轮换中的元素用两两交换的方式归位，最少需要轮换长度-1次。
如果交换的两个元素不是按照轮换顺序来的，那么会导致循环节混在一起。答案一定会更差。

#include <cstdio>

using namespace std;

const int maxn=505, INF=1e9;

int min(int x, int y){ return x<y?x:y; }

void swap(int &x, int &y){

    int t=x; x=y; y=t; }

int n, a[maxn*2], visit[maxn];

int deal(int *array, int id){

    int tot=0, cur;

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

        if (visit[i]!=id){

            cur=i; //cur表示数组编号

            while (visit[cur]!=id){

                visit[cur]=id;

                cur=array[cur];

            }

            ++tot;

        }

    return n-tot;

}

int main(){

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

        int ans=INF;

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

            scanf("%d", &a[i]);

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

            a[i+n]=a[i];

            ans=min(ans, deal(a+i-1, i));

        }

        for (int i=1; i<=(n>>1); ++i)

           swap(a[i], a[n-i+1]);

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

            a[i+n]=a[i];

            ans=min(ans, deal(a+i-1, i+n));

        }

        printf("%d\n", ans);

    }

    return 0;

}

巴特西

uva10570（枚举基准，贪心）

uva10570（枚举基准，贪心）

最新文章

热门文章