POJ 3270-Cow SortingA（Polya定理-交换次数）

布满荆棘的人生 2022-06-17 05:53 126阅读 0赞

Cow Sorting

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;7309</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;2874</td> 
  </tr> 
 </tbody> 
</table>

Description

Farmer John's *N* (1 ≤ *N* ≤ 10,000) cows are lined up to be milked in the evening. Each cow has a unique "grumpiness" level in the range 1...100,000. Since grumpy cows are more likely to damage FJ's milking equipment, FJ would like to reorder the cows in line so they are lined up in increasing order of grumpiness. During this process, the places of any two cows (not necessarily adjacent) can be interchanged. Since grumpy cows are harder to move, it takes FJ a total of *X*\+*Y* units of time to exchange two cows whose grumpiness levels are *X* and *Y*.

Please help FJ calculate the minimal time required to reorder the cows.

Input

Line 1: A single integer: *N*.  
Lines 2.. *N*\+1: Each line contains a single integer: line *i*\+1 describes the grumpiness of cow *i*.

Output

Line 1: A single line with the minimal time required to reorder the cows in increasing order of grumpiness.

Sample Input

3
    2
    3
    1

Sample Output

Hint

2 3 1 : Initial order.  
2 1 3 : After interchanging cows with grumpiness 3 and 1 (time=1+3=4).  
1 2 3 : After interchanging cows with grumpiness 1 and 2 (time=2+1=3).

Source

[USACO 2007 February Gold][]

题目意思:

计算使得N个数有序的最小交换次数。

解题思路【 (๑ŐдŐ)b以下思路 参考原出处不详】

**然后对于一个循环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 \};**

#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<map>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    #define INF 0xfffffff
    #define MAXN 100010
    int a[MAXN],b[MAXN],s[MAXN],t[MAXN],x[MAXN];
    //原数组、置换群、排序数组、循环节、一个置换群内对应的原数组元素
    bool vis[MAXN];
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        int n;
        while(~scanf("%d",&n))
        {
            memset(vis,false,sizeof(vis));
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            memset(s,0,sizeof(s));
            memset(x,0,sizeof(x));
            int sum=0;
            for(int i=0; i<n; ++i)
            {
                scanf("%d",&a[i]);
                s[i]=a[i];
                sum+=a[i];//计算所有元素的和
            }
            int ans=0;
            sort(s,s+n);
            int *m=min_element(a,a+n);//找出所有元素的最小值
            /* for(int i=0; i<n; ++i)
                 cout<<s[i]<<" ";
             cout<<endl;*/
    
            int cnt=0;
            while(1)//计算置换群
            {
                if(cnt==n) break;
                for(int i=0; i<n; ++i)
                    if(a[cnt]==s[i])
                    {
                        b[cnt]=i;
                        ++cnt;
                        break;
                    }
            }
    
            /* for(int i=0; i<n; ++i)
                 cout<<b[i]<<" ";
             cout<<endl;*/
    
            while(1)//分别处理每个循环节
            {
                int cnt=0,i;
                for(i=0; i<n; ++i)
                    if(!vis[i])
                    {
                        vis[i]=true;
                        t[cnt++]=i;
                        break;
                    }
                if(i==n) break;//处理完毕
                int temp=b[t[cnt-1]];
                while(!vis[temp])
                {
                    vis[temp]=true;
                    t[cnt++]=temp;
                    temp=b[t[cnt-1]];
                }
                for(int i=0; i<cnt; ++i)
                    x[i]=a[t[i]];//对应原数组元素
    
                   /*for(int i=0; i<cnt; ++i)
                       cout<<x[i]<<" ";
                   cout<<endl;*/
    
                int *p=min_element(x,x+cnt);
                ans+=min(((cnt-2)*(*p)),((*p)+(cnt+1)*(*m)));
            }
            printf("%d\n",ans+sum);
        }
        return 0;
    }

[USACO 2007 February Gold]: http://poj.org/searchproblem?field=source&key=USACO+2007+February+Gold