题面

解题思路

找环贪心并特判换入最小能否更优

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 100007
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,a[N],p[N],res;
LL sum,size,ans;
bool vis[N];
int main() {
    rint i,j;n=read();
    for(i=1;i<=n;i++) p[i]=a[i]=read();
    sort(p+1,p+n+1);
    for(i=1;i<=n;i++)
        if(!vis[i]) {
            j=i,res=inf,sum=size=0;
            while(!vis[j])
                ++size,sum+=a[j],cmin(res,a[j]),vis[j]=1,j=lower_bound(p+1,p+n+1,a[j])-p;
            ans+=min(sum+res*(size-2),sum+p[1]*(size+1)+res);
        }
    printf("%lld",ans);
    return 0;
}

devil.