【Codeforces 351E 】Jeff and Permutation / Solution

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);
}
Show Comments