POJ 1990（MooFest）经典题目

题目概括：由n头牛，不同的听力值v，当i,j想要通话时，需要max(v(i),v(j))*(dist[i]-dist[j])的volume，问这n*(n-1)/2对牛总共的volume时多少。

题目分析：这里先把各个牛的信息都存放在结构体数组(s[i])里面，然后对这个结构体排序，按volume升序排序。因为这样可以保证先插入的必定比当前这头牛的volume小！首先解决了题目的一个要求，然后就是有效的计算出，各个牛距离当前牛的dist距离和，首先利用树状数组，计算出左边牛的头数(count)和左边牛的x轴坐标和(total)；然后计算出整个区间上牛的坐标和(alltotal)。

根据公式：sum+= s[i].v* [  s[i].x * count - total + alltotal - ( i- count - 1 ) * s[i].x  ] ;

源程序+部分注释：

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#define lowbit(x) (x&(-x))
#define N 20020
using namespace std;

struct node{
	long long v;
	int x;
}s[N];

int cmp(struct node a,struct node b){
	return a.v<b.v;
}

long long sim[N],c[N];

long long getsum(long long t[],int x){
  //因为每个函数都要进行两个操作，分别在不同数组里建图
  //所以要把数组作为参量写入！
	long long sum=0;	
	while(x>0){
		sum+=t[x];
		x-=lowbit(x);
	}
	return sum;
}

int modify(long long t[],int x,long long num){
	while(x<=N){
		t[x]+=num;
		x+=lowbit(x);
	}
	return 0;	
}

int main(){
	long long sum,total,alltotal,count;
	int i,cas;
	while(scanf("%d",&cas)!=EOF){
		sum=0;
		memset(c,0,sizeof(c));
		memset(sim,0,sizeof(sim));
		for(i=1;i<=cas;i++){
			scanf("%lld %d",&s[i].v,&s[i].x);
		}
		sort(s+1,s+1+cas,cmp);
		for(i=1;i<=cas;i++){
			alltotal=getsum(c,20001);
			total=getsum(c,s[i].x);
			count=getsum(sim,s[i].x);
			sum+=s[i].v*(count*s[i].x-total+alltotal-total-s[i].x*(i-count-1));
			modify(c,s[i].x,s[i].x);
			modify(sim,s[i].x,1);
		}
		printf("%lld\n",sum);	
	}
	return 0;
}