51nod1125 交换机器的最小代价

跟做过的bzoj一道置换群的题几乎一样，只是数据范围大了点，那么就用map就好了。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
int read(){
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)) {
        if(c=='-') f=-1;c=getchar();
    }
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x*f;
}
const int nmax=1e5+5;
const int maxn=1e5+5;
const int inf=0x7f7f7f7f;
map<int,int>m;
int a[nmax],to[maxn],b[nmax],mn,n;
bool vis[nmax];
void mins(ll &a,ll b){
    if(a>b) a=b;
}
ll solve(int x){
    ll tmn=a[x],cnt=1,sum=a[x];vis[x]=1;
    for(ll tmp=m[b[x]];tmp!=x;tmp=m[b[tmp]])
      cnt++,mins(tmn,a[tmp]),sum+=a[tmp],vis[tmp]=1;
    return min(sum+(cnt-2)*tmn,sum+tmn+(cnt+1)*mn);
}
int main(){
	n=read(),mn=inf;
	rep(i,1,n) a[i]=b[i]=read(),mn=min(mn,a[i]),m[a[i]]=i;
	sort(b+1,b+n+1);
	ll ans=0;
	rep(i,1,n) if(!vis[i]) ans+=solve(i);
	printf("%lld
",ans);
	return 0;
}

1125 交换机器的最小代价

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

有N台机器重量各不相等，现在要求把这些机器按照重量排序，重量从左到右依次递增。移动机器只能做交换操作，但交换机器要花费一定的费用，费用的大小就是交换机器重量的和。例如：3 2 1，交换1 3后为递增排序，总的交换代价为4。给出N台机器的重量，求将所有机器变为有序的最小代价。（机器的重量均为正整数）

Input

第1行：1个数N，表示机器及房间的数量。（2 <= N <= 50000)
第2 - N + 1行：每行1个数，表示机器的重量Wi。(1 <= Wi <= 10^9)

Output

输出最小代价。

Input示例

Output示例