//算法就是计算每个置换圈内的最小置换总和

#include "stdio.h"
#include "algorithm"
#define MAX 10001

using namespace std;

typedef struct{
	int x;
	int y;
}P;

bool cmp(P a,P b){
	if(a.y<b.y) return true;
	else return false;
}

int min(int a,int b){
	if(a>b) return b;
	else return a;

}

P a[MAX];
int main(){
	int i,j,k;
	int sum,cmin;
	int n;
	int pos[MAX];
	scanf("%d",&n);

	
	for(i=1;i<=n;i++){
		a[i].x=i;
		scanf("%d",&a[i].y);
	}


	sort(a+1,a+n+1,cmp);

	for(i=1;i<=n;i++){
		pos[i]=a[i].x;
	}	
	
	int count;
	int method1,method2;
	int goal=0;
	for(i=1;i<=n;i++){
		if(pos[i]==i) continue;
		sum=0;
		j=i;
		cmin=pos[j];
		count=0;
		while(pos[j]!=j){
			k=pos[j];
			if(k<cmin) cmin=k;
			sum+=a[pos[j]].y;
			
			pos[j]=j;
			j=pos[k];
			count++;
		}
		count++;

		if(cmin==1) goal+=(sum+(count-2)*a[cmin].y);
		else{
			method1=(sum+(count-2)*a[cmin].y);
			method2=(sum+(count+1)*a[1].y+a[cmin].y);
			goal+=min(method1,method2);
		}

	}

	printf("%d\n",goal);

	return 0;
}

• Re:哪位大牛告诉我哪组数据不对呢?我已经试了好多组数据了...算法就是计算每个置换圈内的最小置换总和 (2) phoenixzz 2007-07-22 12:30:58