[BZOJ1697][USACO2007 FEB]Cow Sorting牛排序：贪心+置换

分析

一个月前做的一道题补一下题解，就简单写一写吧。

单独考虑每一个循环节，如果只进行内部的调整，最优方案显然是把最小的绕这个循环交换一圈。

但是借助全局最小值可能使答案更优，两种情况取个(max)就好了。

代码

#include <bits/stdc++.h>
#define rin(i,a,b) for(register int i=(a);i<=(b);++i)
#define irin(i,a,b) for(register int i=(a);i>=(b);--i)
#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)
typedef long long LL;
using std::cin;
using std::cout;
using std::endl;

inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN=10005;
int n,w[MAXN],f[MAXN],minw=1e9;
bool vis[MAXN];

inline bool cmp(int x,int y){
	return w[x]<w[y];
}

int main(){
	n=read();
	rin(i,1,n) w[i]=read(),f[i]=i,minw=std::min(minw,w[i]);
	std::sort(f+1,f+n+1,cmp);
	LL ans=0;
	rin(i,1,n){
		if(vis[i]) continue;
		LL cnt=1,sum=w[i],minww=w[i];
		int now=i;vis[i]=1;
		while(!vis[f[now]]){
			now=f[now];vis[now]=1;
			++cnt;sum+=w[now];minww=std::min(minww,1ll*w[now]);
		}
		ans+=std::min(sum+minww*(cnt-2),
		sum-minww+minw+minw*(cnt-2)+((minw+minww)<<1));
	}
	printf("%lld
",ans);
	return 0;
}