POJ - 1990 MooFest

题意：一排牛，每头牛（坐标pos，听力v），如果牛i和牛j交流的话，需要max{v[i],v[j]}*abs(pos[i]-pos[j])，求两两交流的总和。

思路：还是求逆序数对的思想，按坐标排序后，求当前小于它听力的牛们的总花费，然后倒序后再求一遍就是结果了，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 20005;
#define ll long long 

struct node{
	int pos,v;
}p[MAXN];
int n;
ll dis[MAXN],num[MAXN];

bool cmp(node a,node b){
	return a.pos < b.pos;
}

int lowbit(int x){
	return x&(-x);
}

ll sum(int pos,ll x[]){
	ll ans = 0;
	while (pos > 0){
		ans += x[pos];
		pos -= lowbit(pos);
	}
	return ans;
}

void add(int pos,int num,ll x[]){
	while (pos < MAXN){
		x[pos] += num;
		pos += lowbit(pos);
	}
}

int main(){
	scanf("%d",&n);
	for (int i = 0; i < n; i++)
		scanf("%d%d",&p[i].v,&p[i].pos);
	sort(p,p+n,cmp);
	memset(dis, 0, sizeof(dis));
	memset(num, 0, sizeof(num));
	ll ans = 0;
	for (int i = 0; i < n; i++){
		ans += p[i].v * (p[i].pos*sum(p[i].v, num) - sum(p[i].v,dis));
		add(p[i].v, p[i].pos, dis);
		add(p[i].v, 1, num);
	}
	memset(dis,0,sizeof(dis));
	memset(num,0,sizeof(num));
	for (int i = n-1; i >= 0; i--){
		ans += p[i].v * (sum(p[i].v-1,dis) - p[i].pos*sum(p[i].v-1,num));
		add(p[i].v, p[i].pos, dis);
		add(p[i].v, 1, num);
	}
	cout<<ans<<endl;
	return 0;
}

POJ - 1990 MooFest,布布扣,bubuko.com

POJ - 1990 MooFest

原文：http://blog.csdn.net/u011345136/article/details/22986895