首页 > 代码库 > POJ 3270

POJ 3270

2024-07-27 12:46:58   220人阅读

黑书上的经典题了。我说说解这个题的巧妙的地方吧。

首先，竟然和置换联系起来了。因为其实一个交换即至少可以使其中一个元素到达指定位置了。和循环置换联合起来，使得一个循环内的数可以一步到达指定位置，很巧妙啊。这样，用循环内的最小的数和其它数交换，需要K-1次的交换即可。另外，也可以把整个数列的最小数 i 和循环内的最小数交换，用 i 来和循环内的其他数交换的权值。 两者权值取最小的即可。

 

实在巧妙。

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define LL __int64#define N 10000#define inf (1<<30)using namespace std;int num[N+1];bool vis[N+1];struct Value{	int val,pos;}cow[N+1];bool cmp(Value a,Value b){	if(a.val<b.val) return true;	return false;}LL minL(LL a,LL b){	if(a<b) return a;	return b;}int main(){	int n,res_min,cnt,mi; LL ans,res;	while(scanf("%d",&n)!=EOF){		res_min=inf;		for(int i=1;i<=n;i++){			scanf("%d",&cow[i].val);			cow[i].pos=i;			res_min=min(res_min,cow[i].val);		}		sort(cow+1,cow+n+1,cmp);		for(int i=1;i<=n;i++){			num[cow[i].pos]=i;		}		memset(vis,false,sizeof(vis));		ans=0;		for(int i=1;i<=n;i++){			if(!vis[i]){				int k=i; cnt=0; mi=inf; res=0;				while(!vis[k]){					cnt++;					mi=min(mi,cow[k].val);					res=res+(LL)cow[k].val;					vis[k]=true;					k=num[k];				}				ans=ans+res+minL((LL)(cnt-2)*(LL)mi,(LL)mi+(LL)(cnt+1)*(LL)res_min);			}		}		printf("%I64d\n",ans);	}	return 0;}

　　

POJ 3270


联系
我们