2347331_ac_15ms_216k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MIN(a,b) a<b?a:b
int n;
int num[10001];
int pos[10001];
int vis[10001];
int Tmp[10001];

int cmp(const void *a,const void *b)
{
	return num[*(int *)a]-num[*(int *)b];
}

int main()
{
	int i, j, no, Min;
	int tmp, min, ans;

	scanf("%d",&n);
	Min = 1000000;
	for(i = 0; i < n; i++)
	{
		scanf("%d",&num[i]);
		if(num[i]<Min)
				Min = num[i];
		Tmp[i] = i;

	}
	ans = 0;
	qsort(Tmp,n,sizeof(Tmp[0]),cmp);
	for(i = 0; i < n; i++)
		pos[Tmp[i]] = i;
	for(i = 0; i < n; i++)
	{
		if(pos[i]==i)
		{
			vis[i] = 1;
			continue;
		}
		if(vis[i]==0)
		{
			vis[i] = 1;no = 1;tmp = min = num[i];
			j = pos[i];
			while(1)
			{
				no++;
				vis[j] = 1;
				tmp += num[j];
				if(num[j] < min)
					min = num[j];
				j = pos[j];
				if(j==i)
					break;
			}
			ans += MIN(tmp + (no-2)*min,tmp+(no+1)*Min+min);
		}
	}
	printf("%d\n",ans);
	return 1;
}