POJ 3264 解题报告

本文主要是介绍POJ 3264 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第二道用segment tree过的题。实现还是所有过的里面最慢的。segment tree的实现大同小异，但有人能1s+,2s+的很多,我猜是因为我query的时候都会先进去，如果所求的区间不在这个区间内又跳出，耗费了不少时间。最终险过还真是因为我把cin, cout改成了scanf,printf，这肯定是快了至少400ms的，但我之前已经讲局部变量(输入数据和segment tree)变成了全局变量，不知道这点有多少帮助，理论上讲压栈少了一个元素。

发现从运行时间上来看，vector比array还快了200ms.

3264

Accepted

1968K

4485MS

C++

2799B

/* 
ID: thestor1 
LANG: C++ 
TASK: poj3264 
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>
#include <cstdio>using namespace std;const int MAXN = 50010;
// int heights[MAXN];
std::vector<int> heights(MAXN);
class MaxMin
{
public:int max, min;MaxMin():max(INT_MIN), min(INT_MAX) {}
};// MaxMin segmentTree[4 * MAXN];
std::vector<MaxMin> segmentTree(4 * MAXN);void buildSegmentTree(int left, int right, int index)
{// cout << "[debug]left: " << left << ", right: " << right << ", index: " << index << endl;if (left == right){segmentTree[index].max = max(segmentTree[index].max, heights[left]);segmentTree[index].min = min(segmentTree[index].min, heights[left]);return;}int mid = left + ((right - left) >> 1);buildSegmentTree(left, mid, 2 * index + 1);buildSegmentTree(mid + 1, right, 2 * index + 2);segmentTree[index].max = max(segmentTree[2 * index + 1].max, segmentTree[2 * index + 2].max);segmentTree[index].min = min(segmentTree[2 * index + 1].min, segmentTree[2 * index + 2].min);
}void printSegmentTree(int left, int right, int index)
{cout << "index: [" << index << "] " << segmentTree[index].min << ", " << segmentTree[index].max << endl;if (left != right){int mid = left + ((right - left) >> 1);printSegmentTree(left, mid, 2 * index + 1);printSegmentTree(mid + 1, right, 2 * index + 2);}
}void getMaxMin(int left, int right, const int lindex, const int rindex, int index, int &maxh, int &minh)
{if (left > rindex || right < lindex){return;}if (lindex <= left && right <= rindex){maxh = max(maxh, segmentTree[index].max);minh = min(minh, segmentTree[index].min);return;}int mid = left + (right - left) / 2;getMaxMin(left, mid, lindex, rindex, 2 * index + 1, maxh, minh);getMaxMin(mid + 1, right, lindex, rindex, 2 * index + 2, maxh, minh);
}int main()
{int N, Q;scanf("%d%d", &N, &Q);for (int i = 0; i < N; ++i){scanf("%d", &heights[i]);}buildSegmentTree(0, N - 1, 0);// printSegmentTree(0, N - 1, 0);for (int q = 0; q < Q; ++q){int lindex, rindex;cin >> lindex >> rindex;lindex--, rindex--;int maxh = INT_MIN, minh = INT_MAX;if (rindex - lindex <= 5){for (int i = lindex; i <= rindex; ++i){maxh = max(maxh, heights[i]);minh = min(minh, heights[i]);}}else{getMaxMin(0, N - 1, lindex, rindex, 0, maxh, minh);}printf("%d\n", maxh - minh);}return 0;  
}

这篇关于POJ 3264 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---