放牧代码和思想
专注自然语言处理、机器学习算法
    博主不用扣扣,公事请博客留言,私事请微博私信。开源项目一律GitHub见,发错地方恕不回复,谢谢。

POJ 3264 Balanced Lineup 题解 《挑战程序设计竞赛》

目录

POJ 3264 Balanced Lineup

岳父与小明:农夫约翰有N头牛排成一列,他从第A头牛到第B头牛里挑出最高的那头取名叫岳父,最矮的那头取名叫小明。求岳父与小明的身高差?

3.3活用各种数据结构

线段树和平方分割

平方分割我觉得是一种分治的思想,它所追求的不是分治的最终结果,而是过程的中间结果。将这N头牛平方分割放入sqrt(N)个桶,每个桶只需记录桶里最高和最矮的两个身高值即可。然后完全包含在区间的桶里直接考虑这两个值,否则从原始数据里比较。

唯一需要注意的是这里的下标问题,下标从零开始的话,在求模的时候需要注意:左边界 mod bucket_size == 0时左边界恰好落入桶,(右边界 + 1) mod bucket_size == 0时右边界才恰好落入桶,两者不一样的。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define MAX_N 50000 + 16

int H[MAX_N];	// 输入N头牛的高度
vector<pair<int, int> > bucket; // 对每个桶内高度的最小值与最大值的记录

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int N, Q;
	scanf("%d%d", &N, &Q);
	const int bucket_size = sqrt((float)N);	// error C2668: 'sqrt' : ambiguous call to overloaded function
	bucket.resize(bucket_size + 1);
	for (int i = 0; i < bucket_size + 1; ++i)
	{
		bucket[i].first = 0x3f3f3f3f;
		bucket[i].second = 0x80808080;
	}
	for (int i = 0; i < N; ++i)
	{
		scanf("%d", &H[i]);
		bucket[i / bucket_size].first  = min(bucket[i / bucket_size].first, H[i]);
		bucket[i / bucket_size].second = max(bucket[i / bucket_size].second, H[i]);
	}
	
	for (int i = 0; i < Q; ++i)
	{
		int A, B;
		scanf("%d%d", &A, &B);
		if (A == B)
		{
			puts("0");
			continue;
		}
		int min_height = 0x3f3f3f3f;
		int max_height = 0x80808080;
		int l = A - 1, r = B;
		// 区间两端多出来的部分
		while (l < r && l % bucket_size != 0)
		{
			int h = H[l++];
			min_height = min(min_height, h);
			max_height = max(max_height, h);
		}
		while (l < r && r % bucket_size != 0)
		{
			int h = H[--r];
			min_height = min(min_height, h);
			max_height = max(max_height, h);
		}
		
		// 对每一个桶进行计算
		while (l < r)
		{
			int b = l / bucket_size;
			min_height = min(min_height, bucket[b].first);
			max_height = max(max_height, bucket[b].second);
			l += bucket_size;
		}
		printf("%d\n", max_height - min_height);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////
13143802 hankcs 3264 Accepted 384K 3360MS C++ 1878B 2014-07-23 00:02:58

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

分享到:更多 ()

评论 1

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

    这题目也太搞笑了

    Jecvay3年前 (2014-07-25)回复

我的开源项目

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