Description
Jeff’s friends know full well that the boy likes to get sequences and arrays for his birthday. Thus, Jeff got sequence $p_1,p_2,\cdots,p_n$ for his birthday.
Jeff hates inversions in sequences. An inversion in sequence $a_1, a_2,\cdots,a_n$ is a pair of indexes $i,j (1 ≤ i < j ≤ n)$, such that an inequality $a_i>a_j$ holds.
Jeff can multiply some numbers of the sequence $p$ by $-1$. At that, he wants the number of inversions in the sequence to be minimum. Help Jeff and find the minimum number of inversions he manages to get.
Idea
Considering a number pair $(a_i,a_j)$. If $|a_i|=|a_j|$, there won’t be a inversion definitely. If the case is $|a_i|<|a_j|$, whether a inversion exists will be determined directly by whether $a_j$ is positive or negative.
It turns out that for each $a_i$, let $A$ be the number bigger than it before, and $B$ be the ones after it. The minimum answer is $\sum \min (A_i,B_i).$
Code
#include <bits/stdc++.h>
#define maxn 200100
#define min(a,b) (a<b?a:b)
int t[maxn],a[maxn],b[maxn],cnt[maxn],n,ans;
inline void add(int x,int k){while(x<=n)t[x]+=k,x+=(x&-x);}
inline int sum(int x){int r=0;while(x)r+=t[x],x-=(x&-x);return r;}
int main(){
scanf("%d",&n);
for (register int i=1;i<=n;++i)
scanf("%d",&a[i]),a[i]=abs(a[i]),b[i]=a[i];
std::sort(b+1,b+1+n);
int tot=std::unique(b+1,b+1+n)-b-1;
for (register int i=1;i<=n;++i)
a[i]=std::lower_bound(b+1,b+1+tot,a[i])-b,cnt[a[i]]++;
for (register int i=1;i<=tot;++i) cnt[i]+=cnt[i-1];
for (register int i=1;i<=n;++i){
int A=sum(a[i]-1),B=cnt[a[i]-1]-A;
ans+=min(A,B),add(a[i],1);
}
printf("%d\n",ans);
}