题目

解法

这道题实际上是一类问题：给你两个序列 \(a(n) b(n)\)，问最少花费几步可以将\(a(n)\)变成\(b(n)\)。

如何做这种问题呢？

我们考虑这个步数要最小实际上是什么，就是讲优先级一样的放在两个序列的相同位置，并且尽量让每一个数移动的位置最少。

所以我们需要将\(a(n) 和 b(n)\)按照优先级排序。

那排序后又怎么做呢？

我们考虑构建一个新的数组 \(c(n)\)，其中 \( c[a[i],id] = b[i].id \)。

然后要让 \(a(n)=b(n)\) 实际上就是要让\(c[i]=i\) 也就是要让b数组中第i个数和a数组中第i个数在同一个位置。

那么这就转化成了求解逆序对的数量了。

代码

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define INF 2139062143#define MAX 0x7ffffffffffffff#define del(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long ll;template
              
               inline void read(T&x){ x=0;T k=1;char c=getchar(); while(!isdigit(c)){ if(c=='-')k=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=k;}const int maxn=1e5+15;const int mod=99999997;int n;int temp[maxn];struct node { int h,id; bool operator < (const node& x) const { return h==x.h?id