1006.cpp

第33届ACM亚洲区域赛（哈尔滨赛区预选）1006题目源码

#include<stdio.h>  
#include<string.h>  
long long inv(int n,int a[]){   
  int l = n>>1, r = n-l, i, j;   
  int *v= new int(n);
  long long ret = (r > 1 ? (inv(l , a) + inv(r , a + l)) : 0);   
  for(i = j = 0; i <= l; v[i + j] = a[i], i++)   
  for(ret += j; j < r && (i == l || a[i] > a[l+j]); v[i + j] = a[l + j], j++);   
  memcpy(a, v, sizeof(int)*n);
  return ret;
}
int main(){
	int t, n, i;
	int avg, a[100005], s[100005], tempnum;
	scanf("%d", &t);
	while(t--){
		memset(a, 0, sizeof(a));
		memset(s, 0, sizeof(s));
		scanf("%d %d", &n, &avg);
		s[0] = 0;
		s[n] = 0;
		for(i = 1; i <= n; i++){
			scanf("%d", &a[i]);
			a[i] -= avg;
			s[n - i] = s[n - i + 1] + a[i];
		}
		printf("%lld\n", inv(n + 1, s));
	}
}