POJ 3270(Cow Sorting)

這題主要是交換時要求代價最小
先找到環   相同數字 與   同列 相連
1  第一行為起始序列   第二行為目標序列
  
把一個環中最小的那個與指向的數交換

最後交換3 2

或則調來序列中最小的那個數與環中最小數替換（乘船問題？）

這樣就能得到最優解

ans+=min(  (sizi-2)*mini+sumi,
    (sizi+1)*minn+mini+sumi

[cpp] 
#include<cstdio> 
#include<cmath> 
#include<iostream> 
#include<cstdlib> 
#include<cstring> 
#include<functional> 
#include<algorithm> 
using namespace std; 
#define MAXN (10000+10) 
#define MAXAI (100000+10) 
int n,a[MAXN],a2[MAXN],hpos[MAXAI],ans=0; 
bool b[MAXN]; 
 
int main() 
{ 
//  freopen("cowsorting.in","r",stdin); 
    scanf("%d",&n); 
    for (int i=1;i<=n;i++) scanf("%d",&a[i]); 
    memcpy(a2,a,sizeof(a)); 
    sort(a2+1,a2+1+n,less<int>()); 
    int minn=a2[1]; 
    memset(b,false,sizeof(b)); 
    for (int i=1;i<=n;i++) 
        hpos[a[i]]=i; 
     
         
    for (int i=1;i<=n;i++) 
    { 
//      cout<<a2[i]<<' '<<a[i]<<endl; 
        if (!b[i]&&a2[i]!=a[i]) 
        { 
            b[i]=1; 
            int mini=a[i],start=i,sizi=1,sumi=a[i]; 
            int now=hpos[a2[i]]; 
            while (now!=start) 
            { 
                b[now]=1; 
                sizi++; 
                sumi+=a[now]; 
                mini=min(mini,a[now]); 
                now=hpos[a2[now]]; 
            } 
            ans+=min((sizi-2)*mini+sumi,(sizi+1)*minn+mini+sumi); 
             
        } 
    } 
     
     
     
     
     
///000   
//  for (int i=1;i<=n;i++) printf("%d ",a2[i]); 
///000   
    printf("%d\n",ans); 
     
//  while (1); 
    return 0; 
}