C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 408K, 提交时间: 2022-04-15 09:03:29

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4+10;
typedef pair<int,int>PII;
int n,a[N],b[N],pos[N],mi=N;
bool st[N];
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i],mi=min(mi,a[i]);
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++) pos[a[i]]=i;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(!st[i])
		{
			int j=i,mini=N,cnt=0,sum=0;
			while(!st[j]) 
			{
				st[j]=true;
				mini=min(mini,b[j]);
				sum+=b[j];
				cnt++;
				j=pos[b[j]];
			}
			mini=min(sum+(cnt-2)*mini,sum+(cnt+1)*mi+mini);
			ans+=mini;
		}
	}
 	cout<<ans<<endl;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 600K, 提交时间: 2019-04-04 16:23:15

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10009;
int n,a[maxn],b[maxn],h[maxn],mna,sum;
bool v[maxn];
using namespace std;
int main()
{
	cin>>n;
	mna=maxn;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		mna=min(mna,a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)h[a[i]]=i;
	for(int i=1;i<=n;i++)
	if(!v[i])
	{
		int he=0,mn=maxn,k=0,x=i;
		while(!v[x])
		{
			v[x]=1,mn=min(mn,a[x]);k++;he+=a[x];x=h[b[x]];
		}
		sum+=min(he+(k-2)*mn,he+mn+(k+1)*mna);
	}
	cout<<sum<<endl;
	return 0; 
}