POJ 3270(Cow Sorting)

这题主要是交换时要求代价最小
先找到环 相同数字 与 同列 相连
1 第一行为起始序列 第二行为目标序列

把一个环中最小的那个与指向的数交换

最后交换3 2

或则调来序列中最小的那个数与环中最小数替换（乘船问题？）

这样就能得到最优解

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

[cpp]
#include
#include
#include
#include
#include
#include
#include
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 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< 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;
}