poj-1990 · mfcheer

题目大意：一群牛参加完牛的节日后都有了不同程度的耳聋，第i头牛听见别人的讲话，别人的音量必须大于v[i]，当两头牛i，j交流的时候，交流的最小声音为max{v[i],v[j]}*他们之间的距离。现在有n头牛，求他们之间两两交流最少要的音量和。

解题思路：一开始水水的写了一个n^2的算法，这题终究没有那么白痴。原来是用了树状数组。首先将这n头牛按照v值从小到大排序（后面说的排在谁的前面，都是基于这个排序）。这样，排在后面的牛和排在前面的牛讲话，两两之间所用的音量必定为后面的牛的v值，这样一来才有优化的余地。然后，对于某头牛i来说，只要关心跟排在他前面的牛交流就好了。我们必须快速地求出排在他前面的牛和他之间距离的绝对值只和ans，只要快速地求出ans，就大功告成。这里需要两个树状数组。树状数组可以用来快速地求出某个区间内和，利用这个性质，我们可以快速地求出对于牛i，x位置比i小牛的个数，以及这个牛的位置之和。这里就需要两个树状数组，一个记录比x小的牛的个数a，一个记录比x小的牛的位置之和b，然后，我们可以快速地求出牛i和比牛i位置小的牛的所有距离的绝对值为：a*x[i]-b;也可以方便地求出比牛i位置大的牛到牛i的距离和，即所有距离-b-(i-1-a)*x[i]；那么此题就差不多了。

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<sstream>
#include<time.h>
#include<utility>
#include<malloc.h>
#include<stdexcept>

using namespace std;

int n;

struct q
{
    int v;
    int x;
}p[20005];

int a[20005];
int b[20005];

bool cmp (q a,q b)
{
    if (a.v != b.v)
        return a.v <= b.v;
}

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

void add(int i,int v,int *a)
{
	while (i<=20004)//求所有牛总和
	{
		a[i] += v;
		i+=lowbit(i);
	}
}

int sum (int i,int *a)
{
	long long ans =0;
	while (i>0)
	{
		ans += a[i];
		i-=lowbit(i);
	}
	return ans;
}

int main()
{
	while ( scanf("%d",&n)!=EOF )
	{
		memset (a,0,sizeof(a));
		memset (b,0,sizeof(b));

		for (int i=1;i<=n;i++)
		{
			scanf("%d %d",&p[i].v,&p[i].x);
		}

		sort (p+1,p+1+n,cmp);

		long long  ans = 0;
		long long  dis1;
        long long num1;
        long long alldis=0;

        long long  all=0;;

		for (int i=1;i<=n;i++)
		{
		    dis1 = sum( p[i].x ,a);
		    num1 = sum( p[i].x ,b);

		    ans += p[i].v * ( num1 * p[i].x - dis1 + all- dis1-(i-num1-1)*p[i].x );

		    add( p[i].x , p[i].x ,a);
		    add( p[i].x , 1,b);

		    all += p[i].x;
		}
		printf("%I64d\n",ans);
	}
	return 0;
}

留言