C++14(g++5.4) 解法, 执行用时: 43ms, 内存消耗: 2532K, 提交时间: 2018-08-13 22:20:48

#include <cstdio>
#include <queue>

typedef long long LL;
const int N = 200005;

int n, a[N], tr[N];
LL ans;
std::priority_queue<int> Q;

void Add(int x) {
  for (; x <= n; x += x & -x) ++tr[x];
}
int Query(int x, int re = 0) {
  for (; x; x -= x & -x) re += tr[x];
  return re;
}

int main() {
  scanf("%d", &n);
  n /= 2;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    a[i] /= 2;
    ans += Query(n) - Query(a[i]);
    Add(a[i]);
    Q.push(a[i]);
    if (a[i] < Q.top()) {
      ans += Q.top() - a[i];
      Q.pop();
      Q.push(a[i]);
    }
  }
  printf("%lld\n", ans);
  
  return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 42ms, 内存消耗: 2012K, 提交时间: 2018-08-02 21:04:48

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define LL long long
int n,a[N],tree[N];
LL ans=0;
priority_queue<int>q;
void add(int x){
	for(;x<=n;x+=x&-x)tree[x]++;
}
int sum(int x){
	int ret=0;
	for(;x;x-=x&-x)ret+=tree[x];
	return ret; 
} 
int main(){
	scanf("%d",&n);n/=2;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]/=2;
	for(int i=1;i<=n;i++)
		add(a[i]),ans+=i-sum(a[i]);
	for(int i=1;i<=n;i++){
		q.push(a[i]);
		if(q.top()>a[i])
			ans+=q.top()-a[i],q.pop(),q.push(a[i]);
	}cout<<ans<<endl;
	return 0;
}