传送门

考虑如果能确定每个鞋子最终交换到的位置，那么答案容易算出

具体地，如果原位置为 $i$ 的鞋子要交换到 $pos[i]$ 那么最终答案就是 $pos$ 的逆序对数量

如果不懂可以先去写 NOIP2013火柴排队   我的题解也有关于这个的证明

考虑怎么确定最优的方案，容易想到每个鞋子都找离它最近的鞋子匹配，这样是对的

证明（参考博客）：

设最终相邻的某两对鞋子 $(a,b) (c,d)$，其中$(a,b)$ 表示这一对鞋子初始的位置为 $a,b$，$(c,d)$ 同理，不妨设 $a<c$ ，

如果 $a<b<c<d$ 那么 $(a,b)(c,d)$ 产生的逆序对数量为 $0$，$(c,d)(a,b)$ 产生的逆序对数量为 $4$

如果 $a<c<b<d$ 那么 $(a,b)(c,d)$ 产生的逆序对数量为 $1$，$(c,d)(a,b)$ 产生的逆序对数量为 $3$

如果 $a<c<d<b$ 那么 $(a,b)(c,a)$ 产生的逆序对数量为 $2$，$(c,d)(a,b)$ 产生的逆序对数量为 $2$

所以如果对于某两对相邻鞋子 $(c,d)(a,b)$ ，且 $a<c$，交换他们不会使方案更劣

所以每次贪心选最近的鞋子匹配即可，具体实现看代码

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); } return x*f; } const int N=4e5+; int n,n2,a[N],pos[N]; ll ans; bool vis[N]; vector L[N],R[N];//桶
int t[N];
inline void add(int x,int v) { while(x<=n2) t[x]+=v,x+=x&-x; } inline int ask(int x) { int res=; while(x) res+=t[x],x-=x&-x; return res; } int main() { n=read(); n2=n*; for(int i=;i<=n2;i++) { a[i]=read(); a[i]< ? L[-a[i]].push_back(i) : R[a[i]].push_back(i); } for(int i=;i<=n;i++) { int len=L[i].size(); for(int j=;jR[i][j];//注意细节
}
}
for(int i=;i<=n2;i++) add(i,);
for(int i=;i<=n2;i++)
{
if(vis[i]) continue;
add(i,-); add(pos[i],-);
vis[i]=vis[pos[i]]=;
ans+=ask(pos[i]);//求在它之后的小于等于它的数量
}
//树状数组维护逆序对数量
printf("%lld\n",ans);
return ;
}