poj 3270 Cow Sorting (置换入门)

时间：2022-02-27 11:19:06

题意：给你一个无序数列，让你两两交换将其排成一个非递减的序列，每次交换的花费交换的两个数之和，问你最小的花费

思路：首先了解一下什么是置换，置换即定义S = {1,...,n}到其自身的一个双射函数f。那么我们将其写为若干个不相交的循环的乘积形式(A1, A2, ... Ap1)(B1, B2, ... Bp2)... ...例如

数组   9 4 5 7 3 1

下标   1 2 3 4 5 6

排序后下标   6 3 4 5 2 1

让我们看下标 1->6->1 一个循环 （9 1）

2->3->4->5->2       一个循环（4 5 7 3）、

循环节内的每一个元素都在不合适的位置上，因此长度为l循环节内部至少需要进行（l - 1）次互换可使其有序。

我们可以用一个贪心的思想，每次用循环最小的那个数进行两两交换，定义循环的所有数总和为sum,循环的最小值为k,循环长度为len,那么一个循环的花费为 sum-k+(len-1)*k => sum+(len-2)*k

但是其实还有另一种可能，用整个置换最小的那个和这个循环最小的进行换位，定义循环的所有数总和为sum,循环的最小值为k,循环长度为len，整个置换的最小值为kmin ,,那么一个循环的花费为 sum+(len+1)*kmin+k

每一次循环的最小值为 ans=ans+min(sum+(len-2)*k,sum+(len+1)*kmin+k)

组合数学置换资料https://wenku.baidu.com/view/9b8d9d32e87101f69e3195f8.html

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#define maxn 100005

using namespace std;

struct  node

{

    int num;

    int id;

};

bool cmp(node a,node b)

{

    if(a.num<b.num) return true;

    else return false;

}

int main()

{

    node data[maxn];

    int visit[maxn];

    int n;

    int minn=<<;

    int ans=;

    while(scanf("%d",&n)!=-)

    {

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

      {

        scanf("%d",&data[i].num);

        data[i].id=i;

        minn=min(minn,data[i].num);

      }

      memset(visit,,sizeof(visit));

      sort(data,data+n,cmp);

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

      {

        if(!visit[i])

        {

            visit[i]=;

            int tmp=data[i].id;

            int kmin=data[i].num;

            int sum=data[i].num;

            int len=;

            while(tmp!=i)

            {

               visit[tmp]=;

               len++;

               sum+=data[tmp].num;

               kmin=min(kmin,data[tmp].num);

               tmp=data[tmp].id;

            }

            ans+=min(sum+kmin*(len-),sum+(len+)*minn+kmin);

        }

      }

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

    }

    return ;

}

相关文章