[文章目录]
Description
农夫JOHN准备把他的 N（1 <= N <= 10,000）头牛排队以便于行动。因为脾气大的牛有可能会捣乱，JOHN想把牛按脾气的大小排序。每一头牛的脾气都是一个在1到100，000之间的整数并且没有两头牛的脾气值相同。在排序过程中，JOHN可以交换任意两头牛的位置。因为脾气大的牛不好移动，JOHN需要X+Y秒来交换脾气值为X和Y的两头牛。
请帮JOHN计算把所有牛排好序的最短时间。
%%%hzwer--------http://hzwer.com/3905.html
所以说并不是无脑的找置换群。还有一种借用的情况。
但是能不能借完不还呢？（黑化中。。。）
如果将两个置换群中的两个元素对调（就变成了一个大的置换群），再置换的话（假设x<y），代价为：sum1+sum2+(size1+size2-1)*x;
如果还回去的话，代价为：sum1+sum2+(size1+size2-1)*x;(诶？我好像发现了点什么)；
所以说以上说的借用smallest就是把一些置换群中最小的元素换一圈，构成一个大的置换群，再用smallest置换一圈；
所以说就是将一堆置换群，有些由于自己群内的最小值过大，所以将他们和所有元素中最小的那个元素所在的置换群拼成一个，再用smallest置换一圈就好了233.
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,tmp,size,goal,now,temp;
long long sum,ans;
struct node
{
int data,id,goal;
}a[11000];
bool v[11000];
bool cmp1(node x,node y)
{
return x.data<y.data;
}
bool cmp2(node x,node y)
{
return x.id<y.id;
}
int main()
{
scanf("%d",&n);
temp=1<<30;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i].data);
temp=min(temp,a[i].data);
a[i].id=i;
}
sort(a+1,a+n+1,cmp1);
for(int i=1;i<=n;i++)
a[i].goal=i;
sort(a+1,a+n+1,cmp2);
for(int i=1;i<=n;i++)
{
if(!v[i])
{
v[i]=1;
sum=0;
now=a[i].goal;
goal=i;
if(now==goal) continue;
tmp=a[i].data;
sum+=a[i].data;
size=1;
while(now!=goal)
{
v[now]=1;
if(a[now].data<tmp) tmp=a[now].data;
sum+=a[now].data;
size++;
now=a[now].goal;
}
ans+=sum+min((size-2)*tmp,temp*(size+1)+tmp);
}
}
printf("%lld\n",ans);
return 0;
}