给出数组 ,你可以改变每个数的正负,求逆序对数最少是多少。
,。
考虑一对 ()对逆序对个数的贡献:
- :有贡献当且仅当 取 ;
- :有贡献当且仅当 取 ;
- :有贡献当且仅当 取 , 取 且 ;
暂时先不考虑第三种情况,不难发现 的贡献和 、 中绝对值最大的那个的取值直接挂钩,那么 对逆序对个数的贡献为:
- 时: 且 的 的个数;
- 时: 且 的 的个数;
所以有一个显然的贪心:每个 都从这两个值中取最小的累加进答案。容易发现如果不存在 的 则这个贪心一定是正确的,因为每个 的贡献是独立的。
若存在 的 ,这个贪心其实也是对的。因为对于所有 ,在原序列中一定存在一个分界点 ,满足 的 是负数, 的 是正数。因为 贡献的取值一定是单调的。
代码如下:
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int S=100005;
int n,a[S],id[S];
int tr[S];
inline void add(int pos,int val)
{
for(int i=pos;i<=n;i+=i&-i) tr[i]+=val;
}
inline int que(int pos)
{
int res=0;
for(int i=pos;i>=1;i-=i&-i) res+=tr[i];
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]=abs(a[i]),id[i]=i;
sort(id+1,id+n+1,[&](int x,int y){return a[x]<a[y];});
long long ans=0;
for(int i=1,j=0;i<=n;i++)
{
while(j<i&&a[id[j+1]]!=a[id[i]]) add(id[++j],1);
ans+=min(que(id[i]),j-que(id[i]));
}
printf("%lld\n",ans);
return 0;
}