题解 | 小红的双排列权值

//用两个数组分别记录每个数第一次和第二次出现的位置(第一次a[i]记录,第二次b[i]记录)
//循环一次对应位置b[i]-a[i]-1全部加在一起，就是初始的权值和
//然后我们还可以进行一次交换操作，采用贪心的策略，每次把最大的a[i]换最小的b[i]，可以实现最大化权值和。
//如果最大的a[i]比最小的b[i]还小那就不换，换了权值和会变小。
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() 
{
    int n;
    cin>>n;
    vector<int> a(n+1);
    vector<int> b(n+1);
    for(int i=1;i<=2*n;i++){
        int x;
        cin>>x;
        if(a[x]==0) a[x]=i;
        else b[x]=i;
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=b[i]-a[i]-1;
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
  	if(a[n]>b[1])
    ans+=2*(a[n]-b[1]);
    cout<<ans<<'\n';
    return 0;
}