放牧代码和思想
专注自然语言处理、机器学习算法

POJ 1990 MooFest 题解 《挑战程序设计竞赛》

目录

POJ 1990 MooFest

奶牛节:N头奶牛每头耳背程度v,坐标x。两牛交流需要音量为distance * max(v(i),v(j)),求所有牛两两交流所需总和?

3.3活用各种数据结构

Binary Indexed Tree

要求{∀i with v[i]<v[j]} Σv[j]*|x[i]-x[j]|,也就是求 Σv[j]*(x[j]-x[i]){∀i with v[i]<v[j] and x[i]<x[j]} + Σv[j]*(x[i]-x[j]){∀i with v[i]<v[j] and x[j]<x[i]}。这里涉及到求和,而且求和的区间有重复,所以要利用树状数组。

这题用到了两个BIT,分别是个数BIT和距离BIT。将牛按照耳背程度升序后,一头一头地加入奶牛节。加入每一头的时候,这头牛的耳背程度肯定是最大的。那么就用这头牛的耳背程度乘以到所有牛的距离即可。每加入一头牛,就逐步构建BIT一次。

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_N 20000 + 16
typedef long long LL;

pair<int, int> cow[MAX_N];
int N;
LL count_bit[MAX_N], distance_bit[MAX_N];	// 两个数组下标都是坐标,值用来统计牛的个数和距离

// 求和sum{a[t], 0 <= t <= i}
LL sum(LL* bit, int i)
{
	LL s = 0;
	while (i > 0)
	{
		s += bit[i];
		i -= i & -i;
	}

	return s;
}

// 求和a[from, to)
LL sum(LL* bit, int from, int to)
{
	return sum(bit, to - 1) - sum(bit, from - 1);
}

// 执行 a[i] += x
void add(LL* bit, int i, LL x)
{
	while (i <= MAX_N)
	{
		bit[i] += x;
		i += i & -i;
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> cow[i].first >> cow[i].second;
	}

	sort(cow, cow + N);
	LL result = 0;
	for (int i = 0; i < N; ++i)
	{
		// cow按v升序,v始终为最大
		int v = cow[i].first, x = cow[i].second;	// 自己的参数,取个短点好懂的名字
		LL left = sum(count_bit, 1, x), right = sum(count_bit, x + 1, MAX_N);	// 左右牛的个数
		result += v * ((left * x - sum(distance_bit, 1, x)) + (sum(distance_bit, x + 1, MAX_N) - right * x));
		add(count_bit, cow[i].second, 1);
		add(distance_bit, cow[i].second, cow[i].second);
	}
	cout << result << endl;

#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////
12948268 hankcs 1990 Accepted 692K 172MS C++ 1529B 2014-06-05 00:57:32

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 1990 MooFest 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    只能说写得太好了,看其他人的都理解不到那个公式

    idaplb2年前 (2015-12-19)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机