C++11(clang++ 3.9) 解法, 执行用时: 31ms, 内存消耗: 1636K, 提交时间: 2020-02-26 21:02:42

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
#define M 100005
using namespace std;
int num[M],P[M],A[M];
void Add(int x)
{
	for(;x<M;x+=lowbit(x))
	num[x]++;
}
int Query(int x)
{
	int res=0;
	for(;x;x-=lowbit(x)) res+=num[x];
	return res;
}
int main()
{
	int n,x;
	long long cnt=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&x),P[x]=i,A[i]=x;
	for(int i=1;i<=n;i++)
	{
		Add(A[i]);
		cnt+=i-Query(A[i]);
	 } 
	 long long ans=cnt;
	 for(int i=1;i<n;i++)
	 {
	 	cnt+=n-2*P[i]+1;
	 	ans=min(ans,cnt);
	 }
	 printf("%lld\n",ans);
	 return 0;
}

C++14(g++5.4) 解法, 执行用时: 28ms, 内存消耗: 1976K, 提交时间: 2019-10-19 11:26:52

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int n,pos[110000],c[110000],f[110000];
long long ans,te;
inline int ask(int x){
	int ans=0;
	while (x){
		ans+=f[x];
		x-=x&(-x);
	}
	return ans;
}
inline void add(int x){
	while (x<=n){
		f[x]++;
		x+=x&(-x);
	}
}
int main(){
	scanf("%d",&n);
	fo(i,1,n){
		scanf("%d",&c[i]);
		pos[c[i]]=i;
	}
	fd(i,n,1){
		ans+=ask(c[i]-1);
		add(c[i]);
	}
	te=ans;
	fo(i,1,n-1){
		te+=(n-pos[i])-(pos[i]-1);
		if (te<ans) ans=te;
	}
	printf("%lld\n",ans);
	return 0;
}