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//////////////////////////////////

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