题解 P2091 【排序】

貌似没什么人做，来写一篇题解

首先，我们拆出给定序列的置换与$\left ( 1,2,3\dots,n \right )$这个置换的循环

然后，对于每一个循环，计算循环内部的答案

我们先定义全局最小值为$Min$，循环内部最小值为$M$，循环中数的总和为$S$，循环中数的数量为$cnt$，则可能的交换方式有：

1. 用$M$一个一个与别的数交换，所需的体力值为：

$M*(cnt-2)+S$

2. 将全局最小值与循环内部最小值交换，然后用全局最小值与别的数交换，最后再将全局最小值和循环内部最小值交换，所需体力值为：

$Min*(cnt+1)+S+M$

对于每个循环，将两种方法的最小值加到总答案里就行了。
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
ll read(){
	ll x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){
		x*=10;x+=ch-'0';
		ch=getchar();
	}
	return x;
}
ll a[200005],wz[200005],val[200005];
bool book[200005];
int main(){
	ll n,cnt,ans,minn,S,minm=2147483647;
	bool bj;
	cin>>n;
	for(int i=1;i<=n;i++){
		a[i]=read();
		wz[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		val[i]=read();
		minm=min(minm,val[i]);
	}
	ans=0;
	for(int i=1;i<=n;i++){
		if(!book[a[i]]){
			int x=i;
			cnt=0;S=0;
			minn=2147483647;
			while(!book[a[x]]){
				book[a[x]]=1;
				S+=val[x];cnt++;
				minn=min(minn,val[x]);
				x=wz[x];
			}
			ans+=min(minn*(cnt-2)+S,minm*(cnt+1)+S+minn);
		}
	}
	cout<<ans<<endl;
	return 0;
}