POJ 1990(MooFest)经典题目

spoiler posted @ 2011年4月11日 21:51 in 树状数组经典题目 , 1386 阅读

题目概括:由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;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter