考虑如果能确定每个鞋子最终交换到的位置，那么答案容易算出
具体地，如果原位置为 $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<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=4e5+7; int n,n2,a[N],pos[N]; ll ans; bool vis[N]; vector <int> 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=0; while(x) res+=t[x],x-=x&-x; return res; } int main() { n=read(); n2=n*2; for(int i=1;i<=n2;i++) { a[i]=read(); a[i]<0 ? L[-a[i]].push_back(i) : R[a[i]].push_back(i); } for(int i=1;i<=n;i++) { int len=L[i].size(); for(int j=0;j<len;j++) { pos[L[i][j]]=R[i][j]; pos[R[i][j]]=L[i][j]; ans+=L[i][j]>R[i][j];//注意细节 } } for(int i=1;i<=n2;i++) add(i,1); for(int i=1;i<=n2;i++) { if(vis[i]) continue; add(i,-1); add(pos[i],-1); vis[i]=vis[pos[i]]=1; ans+=ask(pos[i]);//求在它之后的小于等于它的数量 } //树状数组维护逆序对数量 printf("%lld ",ans); return 0; }