题解 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;
}