题解 | 小红的双排列权值

//我们可以假设最后需要换的值对应的下标为a1,a2,b1,b2;
//然后分讨这四个下标的相对位置即可
//最后发现是交换最后一个第一次出现，和第一个第二次出现的值的位置
#include<iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include<vector>
#include <string>
#include<functional>
#include <set>
#include<bitset>
#include<climits>
#include<queue>
using namespace std;
#define int long long
#define itn long long
#define for1 for(int i=1;i<=n;i++)
#define for0 for(int i=0;i<n;i++)
#define dl delete []
int fx[] = { -1,0,1,0 };
int fy[] = { 0,1,0,-1 };
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   

    int n;
    cin >> n;
    int* p = new int[2 * n + 1];
    int * first = new int[n + 1];
    int* second = new int[n + 1]; 
        fill(first, first + n + 1, 0);
        fill(second, second + n + 1, 0);
        int a = 0;
        int b = 0;
        bool bo0 = 0;
        bool bo1 = 0;
        //b第一个第二次出现和a最后一个第一次出现;
    for (int i = 1; i <= 2 * n; i++)
    {

        cin >> p[i];
        if (first[p[i]] == 0)
        {
            a = p[i];
            first[p[i]] = i;

        }
        else
        {
            if (bo0 == 0)
            {
                b = p[i];
                bo0 = 1;
            }
            second[p[i]] = i;

        }

   


    }


    int index = first[a];
    int index2 = second[b];
    p[index2] = a;
    p[index] = b;

    first[a] = index2;
    second[b] = index;


    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += second[i] - first[i] - 1;
    }
    cout << ans << endl;

  
   
}