本文共 1491 字，大约阅读时间需要 4 分钟。

题目

思路

假设两个数字 $x,y$ 满足 $|x|<|y|$ ，则何如？

若 $y$ 选择了负数，无论 $x$ 选正还是负，都大于 $y$ 。反之，若 $y$ 选择正数，则一定大于 $x$ 对应的数。

于是我们得出结论，对两个数字的大小比较只跟绝对值较大者的选择有关。所以我们将每个逆序对的贡献都放到绝对值较大者身上，直接在选正数、选负数中取 $\mathtt{m}\mathtt{i}\mathtt{n}$ 即可。

绝对值相等的呢？不难发现，越靠前，越容易选择负数；越靠后，越容易选择正数。于是绝对值相同就会自动的有序（即，形如 $-x,-x,-x,x,x$ ，其中 $x$ 为正），不贡献逆序对。

然后做完了。

代码

#include <cstdio>#include <iostream>#include <vector>#include <algorithm>using namespace std;inline int readint(){   	int a = 0; char c = getchar(), f = 1;	for(; c<'0'||c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c&&c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}template < typename T >void getMax(T&a,const T&b){   if(a<b)a=b;}template < typename T >void getMin(T&a,const T&b){   if(b<a)a=b;}const int MaxN = 2005;struct Node{   	int val, id;	bool operator < (const Node &that) const {   		return val < that.val;	}} node[MaxN]; int c[MaxN];int main(){   	int n = readint();	for(int i=1; i<=n; ++i){   		node[i].val = readint();		if(node[i].val < 0)			node[i].val *= -1;		node[i].id = i;	}	sort(node+1,node+n+1);	int ans = 0; node[n+1].val = 1000000;	for(int l=1,r=0; l<=n; l=r+1){   		while(node[r+1].val == node[l].val)			++ r;		for(int i=l; i<=r; ++i){   			int sum = 0, t = node[i].id;			for(int j=t; j; j-=(j&-j))				sum += c[j];			ans += min(sum,(l-1)-sum);		}		for(int i=l; i<=r; ++i){   			int t = node[i].id;			for(int j=t; j<=n; j+=(j&-j))				++ c[j];		}	}	printf("%d\n",ans);	return 0;}