首页 > 代码库 > poj 3270 Cow Sorting(初涉置换群)

poj 3270 Cow Sorting(初涉置换群)

http://poj.org/problem?id=3270


大致题意:给出n个整数,要将它们转化成递增序列,每交换其中两个数的代价是这两个数之和。问排序成功后的最小代价。


该题考察的是置换群知识。在黑书p247上有详细的讲解。总结下置换群,方便复习。


群:给定一个集合G={a,b,c...}和集合G上的二元运算 ·,如果满足封闭性,结合律,存在单位元和逆元,则成集合G在运算‘·‘之下是一个群。


置换:n个元素1,2,....,n之间的置换可表示为 

1     2     3     ...     n

a1  a2   a3   ...     an

表示1被1到n中的某个数a1代替,2被1到n中的某个数a2代替,直到n被1到n中的某个数an代替,且a1,a2....an互不相同。


置换群:是若干置换的集合。运算是置换的连接。


                                            a1    a2    a3    ....    an

循环:记(a1,a2...an) =       a2    a3    a4     ....    a1   称为n阶循环。每个置换都可以写成若干个循环的乘积。


例如置换1    2    3    4    5    6    = (1 3 6 )(2 5 )(4)

               3    5   6    4     2    1 

 置换的循环节数就是上述循环的个数,例如上面循环节数就是3。


回到本题。例如有一个序列: 1  8  9  7  6

要将  1  8  9  7  6 变成有序序列 1  6  7  8  9,可以看做要完成一个置换  

1   8   9   7   6

1   6   7   8   9

因为每个置换都可看做若干轮换(循环)的乘积,那么上述置换可表示成两个循环(1)(6,7,8,9)的乘积。而我们的目的是变成循环(1)(6)(7)(8)(9),所以每次对换一定是在同一个循环中的两个元素之间进行。


然后对于一个循环i,设它的长度是ki,那么它至少要交换ki-1次,即每次让一个元素到达目标位置。既然交换次数一定,那么要使交换的代价最小,就是每次都拿循环里最小的元素ti与其他元素交换。根据这些知识,我们得知解决原题,有两种方案:

1.对于每个循环,都那该循环里最小的元素ti与其他元素交换,那么共花费 sumi + (ki-2)*ti,(sumi是该循环个元素之和)

2.让ti先和n个元素中最小的元素m交换,让m进入该循环,并和剩下的ki-1个元素依次交换把他们送入目标位置,然后再让m和ti交换,ti退出该循环。这样共花费 sumi + ti + (ki+1)*m


综上:所有循环都交换完所需的最小花费cost = sum + ∑min{ (ki-2)*ti , ti + (ki+1)*m };

对于求各个循环,拿两个数组来回记录一下就可以了。由上式可以看出我们只需记录每个循环的ki(长度)和ti(最小元素)。


#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;

struct node
{
    int num;
    int Min;
}ans[10010]; //记录每个循环的长度和最小元素


int main()
{
    int n,a[10010],b[1000010];
    int vis[1000010];
    int cnt,Min;
    int i,t;
    int ans_num;
    int sum;
    int Minn;

    while(~scanf("%d",&n))
    {
        sum = 0;
        Minn = INF;

        for(i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            sum += a[i];
            b[a[i]] = i;
            Minn = min(Minn,a[i]); //n个数中的最小数
        }
        sort(a+1,a+1+n);

        memset(vis,0,sizeof(vis));
        ans_num = 0;
        while(1)
        {
            //每次找出一个未被访问的数,从这个数开始找其所在的循环
            for(i = 1; i <= n; i++)
                if(!vis[a[i]])
                    break;
            if(i > n)
                break;
                
            cnt = 0; //该循环的元素个数
            Min = INF;//该循环中最小的元素
            t = a[i];
            
            while(1)
            {
                vis[t] = 1;
                Min = min(Min,t);
                cnt++;
                if(!vis[a[b[t]]])
                    t = a[b[t]];
                else break;
            }
            ans[++ans_num] = (struct node){cnt,Min};
        }
        
        for(int i =1; i <= ans_num; i++)
        {
           int num = ans[i].num;
           int Min = ans[i].Min;
           sum += min((num-2)*Min, Min + (num+1)*Minn);
        }
        printf("%d\n",sum);

    }
    return 0;
}