欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

清华数据结构平均气温AC100

程序员文章站 2022-03-22 18:01:40
...

写在最前:

这道题,其实最节约时间的算法应该是用FC tree,用该数据结构可以在logn的时间内算出来。

但是,说实话,我写不出这样的树出来,至少目前没必要,因为这样太麻烦了,关键是指针不好指。

所以,我用的是2d range tree。用该数据结构可以在logn^2的时间内算出来!

该数据结构的思想为:

1)先创建AVL树,树的每个节点为站点值

2)将站点按x进行从小到大排序,排序完毕之后,依次插入AVL树的叶子节点中。

并且,站点数组的每个数据留一个指针指向最后的叶子节点,方便后面查找用

同时,还将y数组排序好了给每一个节点!

这一段不看也没事

(这里比较神奇的是,最后插完,刚好只有一个叶子节点的一个右孩子是未被插入的,这个在数学上也是可以解释的,因为叶子的孩子节点数之和刚好比总结点数多1)

解释如下:n个节点,有2n个孩子指针。而2n个孩子指针,需要指向n-1个节点(其中有一个被根节点指了),因此剩余n+1个孩子指针。故再次插入n个节点后,剩余1个指针。而我们插入的顺序是由左至右,即由小到大,故最右边的叶子节点的右孩子指针为空。

 

3)对于每个X1,X2,Y1,Y2。这里我们对x进行2分查找,找到后即可通过预留的指针找到对应的最末端叶子节点

4)然后顺次走到根节点,只需做的是root=root->parent。

这里需要注意的是,每向上走一步,要留一个指针指向原来的位置,这样我们要是想从交点处回来,也方便!

5)找到x1,x2对应的共同节点,然后共同节点往下走,查找每个节点对应的左子树或者右子树即可!

6)对于每颗右子树或者左子树,他们的x值是不用管的,肯定满足,但是y值是要用二分查找找到的,因此需要花费logn的时间

查找到一个y值,就+它的气温,最后得到总气温了!

如果思路还是看不懂,可以详见https://blog.csdn.net/liuqiyao_01/article/details/8478719

或者看图

清华数据结构平均气温AC100清华数据结构平均气温AC100

 最后,附上代码!

#pragma warning(disable:4996)
#include <stdio.h>
#include "temperature.h"
#define maxn 50000
using namespace std;
struct range_node;//范围查询的节点构成范围查询树
//station_type是每一个观测站的具体内容(包括了x,y坐标,温度temp,
//观测站内部还有一个指针c,是用来指向叶子节点,然后用来回溯路径)
//一个指针road,用来指向前一个节点
typedef struct _station_type
{
	int x, y;
	int temp;
	_station_type&operator=(const _station_type&data)
	{
		temp = data.temp;
		x = data.x;
		y = data.y;
		return *this;
	}
	range_node*c,*road=NULL;
} station_type;
station_type stations[maxn];
//fctree是用来构建y值数组,每个fctree中都含有station_type类型的data
//y值比较大小,当y值相同时,看x值,这里不可能出现x与y值相同
struct fctree {
	station_type data;
	bool operator>(const fctree&a)
	{
		if (data.y > a.data.y)return true;
		else if (data.y == a.data.y) {
			if (data.x > a.data.x)return true;
			else return false;
		}
		else return false;
	}
	bool operator<(const fctree&a)
	{
		if (data.y < a.data.y)return true;
		else if (data.y == a.data.y) {
			if (data.x < a.data.x)return true;
			else return false;
		}
		else return false;
	}
};
//每个节点都有左右指针和对应的y值
//首先要构建AVL树
struct range_node {
	range_node*rc, *lc, *parent;
	fctree*fc;//这个指针用于指向y数值的数组,记得初始化时要用new fc来确定它的数组大小
	int fc_size = 0;
	station_type data;//每个节点中都只有一个数据点
	int height = 0;
	range_node() { rc = lc = NULL; fc = NULL; parent = NULL; }
	range_node(const station_type&e, range_node*p, fctree*fc1 = NULL, range_node*lc1 = NULL, range_node*rc1 = NULL) :data(e), parent(p), fc(fc1), lc(lc1), rc(rc1) {}
};

//构建AVL树---------------------------------------------------------
struct rangetree {
	//所包含的数据成员;
	rangetree() { range_node(); }
	range_node*_hot;//待插入点的父亲节点
	range_node*_root;//根节点
	range_node*&search(const int&e);
	void insertAsRoot(const station_type&e);
	range_node*insert(const station_type&data);
	range_node*&fromparento(range_node*g);
	range_node*connect34(range_node*a, range_node*b, range_node*c, range_node*t0, range_node*t1, range_node*t2, range_node*t3);
	range_node*rotateAt(range_node*g);
	void search_leaf(range_node*&v, int&i, range_node*hot);
	int size = 0;
};
//_station_type的相等是要求x和y都相等
bool operator==(const _station_type&data1, const _station_type&data2)
{
	return ((data1.x == data2.x) && (data1.y == data2.y));
}
int stature(range_node*a) { return a ? a->height : -1; }//由于a可能为空,因此需要单独给它一个函数
void rangetree::insertAsRoot(const station_type&e)
{
	_root = new range_node(e, NULL); size++;
}
range_node*&searchin(range_node*&v, const int&e, range_node*&hot)
{
	if (!v)return v;
	hot = v;
	return searchin((e <= v->data.x) ? v->lc : v->rc, e, hot);
}
range_node*&rangetree::search(const int&e)
{
	//有了_hot=NULL后,就不用每次查询都把_hot重新更新了
	return searchin(_root, e, _hot = NULL);
}
bool Balance(range_node a) { return (stature(a.lc) - stature(a.rc)) > -2 && stature(a.lc) - stature(a.rc) < 2; }
bool islchild(range_node*g) { return g->parent && (g->parent->lc == g); }
bool isrchild(range_node*g) { return g->parent && (g->parent->rc == g); }
void updateheight(range_node*g)
{
	if (stature(g->lc)>stature(g->rc)) { g->height = stature(g->lc) + 1; }
	else { g->height = stature(g->rc) + 1; }
}
range_node*tallerchild(range_node*g)
{
	return (stature(g->lc) > stature(g->rc)) ? g->lc : (((stature(g->lc) <stature(g->rc)) ? g->rc : (islchild(g) ? g->lc : g->rc)));
}
range_node*&rangetree::fromparento(range_node*g)
{
	if (g->parent) { return islchild(g) ? g->parent->lc : g->parent->rc; }
	else { return _root; }
}
range_node*rangetree::insert(const station_type&data)
{
	range_node*&x = search(data.x);
	//x不能改变,因为x是引用,x改变,则其父节点的孩子指针也跟着改变,故为了安全起见,不能改变;
	range_node*xx = x = new range_node(data, _hot);
	for (range_node*g = _hot; g; g = g->parent)
	{
		if (!Balance(*g)) {
			auto&temp = fromparento(g);//=rotateAt(tallerchild(tallerchild(g)));
									   //auto p = tallerchild(g);
									   //auto v = tallerchild(p);
			temp = rotateAt(tallerchild(tallerchild(g)));
			break;
		}
		else updateheight(g);
	}
	size++;
	return xx;
}
range_node*rangetree::connect34(range_node*a, range_node*b, range_node*c, range_node*t0, range_node*t1, range_node*t2, range_node*t3)
{
	a->lc = t0; if (t0) { t0->parent = a; }// printf("a->lc= %d\n", a->lc->data.x);
	a->rc = t1; if (t1) { t1->parent = a; }//printf("a->rc= %d\n", a->rc->data.x);
	updateheight(a);
	c->lc = t2; if (t2) { t2->parent = c; } //printf("c->lc= %d\n", c->lc->data.x);
	c->rc = t3; if (t3) { t3->parent = c; }// printf("c->rc= %d\n", c->rc->data.x);
	updateheight(c);
	b->lc = a; a->parent = b;
	b->rc = c; c->parent = b; updateheight(b);
	return b;
}
range_node*rangetree::rotateAt(range_node*v)
{
	range_node*p = v->parent;
	range_node*g = p->parent;
	if (islchild(p)) {
		if (islchild(v)) {
			p->parent = g->parent;//别忘了parent指针也要记得更新!
			return connect34(v, p, g, v->lc, v->rc, p->rc, g->rc);
		}
		else
		{
			v->parent = g->parent;
			return connect34(p, v, g, p->lc, v->lc, v->rc, g->rc);
		}
	}
	else {
		if (islchild(v)) {
			v->parent = g->parent;
			return connect34(g, v, p, g->lc, v->lc, v->rc, p->rc);
		}
		else {
			p->parent = g->parent;
			return connect34(g, p, v, g->lc, p->lc, v->lc, v->rc);
		}
	}
}
//AVL树构建完毕---------------------------------------------------------

bool isleaf(range_node*root) {
	return root && (!root->lc && !root->rc);
}
int n;
long long int  record = 0;
int count;
station_type stack_x1[100], stack_x2[100];
int road_x1, road_x2;
void merge_y(fctree*&a1, fctree data_lc[], fctree data_rc[], int n_lc, int n_rc)
{
	a1 = new fctree[n_lc + n_rc];
	int i = 0, j = 0, k = 0;
	while (i < n_lc&&j < n_rc)
	{
		if (data_lc[i] < data_rc[j])a1[k++].data = data_lc[i++].data;
		else a1[k++].data = data_rc[j++].data;
	}
	if (i == n_lc)
		while (k<n_lc + n_rc)
		{
			a1[k++].data = data_rc[j++].data;
		}
	else
		while (k<n_lc + n_rc)
		{
			a1[k++].data = data_lc[i++].data;
		}
}
//查找叶子节点并且插入对应的x值节点,注意,每插完一次,每个节点的y值也会更新一次
//节点用fctree装y值
void rangetree::search_leaf(range_node*&v, int&i, range_node*hot)
{
	if (!v) {
		if (i < n)
		{
			stations[i].c = v = new range_node(stations[i], hot);
			v->fc = new fctree[1]; 
			v->fc->data = stations[i++];
			(v->fc_size)++;
		}
	}
	else {
		hot = v;
		search_leaf(v->lc, i, hot);
		search_leaf(v->rc, i, hot);
		if (v->lc && v->rc)
		{
			merge_y(v->fc, v->lc->fc, v->rc->fc, v->lc->fc_size, v->rc->fc_size);
			v->fc_size = v->lc->fc_size + v->rc->fc_size;
		}
		else
		{
			v->fc = new fctree[v->lc->fc_size];
			for (auto i = 0; i < v->lc->fc_size; i++)v->fc[i].data = v->lc->fc[i].data;
			v->fc_size = v->lc->fc_size;
		}
	}
}
//用于对x进行2分查找
void merge_x(station_type data[], int lo, int mi, int hi)
{
	station_type*a1 = new station_type[mi - lo];
	int k = lo, i = 0, t = mi - lo;
	for (auto i = 0; i < mi - lo; i++)a1[i] = data[k++];
	while ((mi< hi) && (i<t))
	{
		if (a1[i].x < data[mi].x)data[lo++] = a1[i++];
		else if (a1[i].x == data[mi].x&&a1[i].y < data[mi].y)data[lo++] = a1[i++];
		else data[lo++] = data[mi++];
	}
	if (i == t);
	else while (lo < hi)data[lo++] = a1[i++];
	delete[]a1;
}
void mergesort_x(station_type data[], int lo, int hi)
{
	int mi;
	if (hi - lo > 1) {
		mi = (hi + lo) >> 1;
		mergesort_x(data, lo, mi);
		mergesort_x(data, mi, hi);
		merge_x(data, lo, mi, hi);
	}
	else return;
}
//寻找x1和x2
void search_x1(range_node*root, int x1, int x2, station_type stack[], int&road, int lo, int hi)
{
	int lenght = hi;
	while (hi > lo)
	{
		int mi = (hi + lo) >> 1;
		(stations[mi].x<x1) ? lo = mi + 1 : hi = mi;
	}
	if (lo<lenght&& stations[lo].x <= x2) {
		auto root = stations[lo].c;
		while (root)
		{
			stack[road] = root->data;
			stack[road].c = root;
			if (!isleaf(stack[road].c))stack[road].road = stack[road - 1].c;
			road++;
			root = root->parent;
			
		}
	}
	else;
}
void search_x2(range_node*root, int x1, int x2, station_type stack[], int&road, int lo, int hi)
{
	int lenght = hi;
	while (hi > lo)
	{
		int mi = (hi + lo) >> 1;
		(stations[mi].x > x2) ? hi = mi : lo = mi + 1;
	}
	--lo;
	if (lo > -1 && stations[lo].x >= x1) {
		auto root = stations[lo].c;
		while (root)
		{
			stack[road] = root->data;
			stack[road].c = root;
			if (!isleaf(stack[road].c))stack[road].road = stack[road - 1].c;
			road++;
			root = root->parent;
		}
	}
	else;
}
//寻找每条路径的公共节点,从该节点开始回溯
range_node*common_root()
{
	while (0 < road_x1 && 0 < road_x2&&stack_x1[--road_x1] == stack_x2[--road_x2]);
	return (stack_x1[road_x1] == stack_x2[road_x2]) ? stack_x1[road_x1].c : stack_x1[++road_x1].c;
}
//对每个节点的y值进行2分查找!
void search_y(range_node*root, int lo, int hi, int y1, int y2)
{
	while (lo < hi)
	{
		int mi = (lo + hi) >> 1;
		(y1 <= root->fc[mi].data.y) ? hi = mi : lo = mi + 1;
	}
	while (lo < root->fc_size&&root->fc[lo].data.y <= y2  )
	{
		record += root->fc[lo].data.temp;
		count++;
		lo++;
	}
}
void travelReport(int x1,int x2,int y1, int y2)
{
	while (road_x1 >= 0)
	{
		auto rc = stack_x1[road_x1].c->rc;
		auto lc = stack_x1[road_x1].c->lc;
		auto road = stack_x1[road_x1].road;
		if (rc&&rc!=road)search_y(rc, 0, rc->fc_size, y1, y2);
		road_x1--;
	}
	auto now = stack_x1[road_x1 + 1].c;
	if (now->data.x >= x1 &&now->data.x <= x2 && now->data.y >= y1 && now->data.y <= y2)
	{
		count++;
		record += now->data.temp;
	}
	while (road_x2 >= 0)
	{
		auto rc = stack_x2[road_x2].c->rc;
		auto lc = stack_x2[road_x2].c->lc;
		auto road = stack_x2[road_x2].road;
		if (lc&&lc != road)search_y(lc, 0, lc->fc_size, y1, y2);
		road_x2--;
	}
	auto now2 = stack_x2[road_x2 + 1].c;
	if (now2->data.x >= x1 && now2->data.x <= x2 && now2->data.y >= y1 && now2->data.y <= y2)
	{
		count++;
		record += now2->data.temp;
	}
}
//先序和中序遍历用来保证AVL树的正确构建-----------------------------------------------------------------
void xianxutravel(range_node*r)
{
	printf("%d(%d)\n", r->data.x, r->data.y);
	if (r->lc)xianxutravel(r->lc);
	if (r->rc)xianxutravel(r->rc);
}
void midtravel(range_node*r)
{
	if (r->lc)midtravel(r->lc);
	printf("%d(%d)\n", r->data.x, r->data.y);
	if (r->rc)midtravel(r->rc);
}
int main()
{
	n = GetNumOfStation();
	if (n == 0) {
		int x1, x2, y1, y2;
		while (GetQuery(&x1, &y1, &x2, &y2)) {
			Response(0); printf("0\n");
		}
		return 0;
	}
	rangetree a;
	for (auto i = 0; i < n; i++)GetStationInfo(i, &(stations[i].x), &(stations[i].y), &(stations[i].temp));
	a.insertAsRoot(stations[0]);
	for (auto i = 1; i < n; i++)a.insert(stations[i]);
	//为了防止出现先大的插入导致后面小的没有位置,所以得先排序;

	mergesort_x(stations, 0, n);
	int i = 0;
	a._hot = NULL;
	a.search_leaf(a._root, i, a._hot);
	//先序和中序遍历
	//midtravel(a._root);
	//printf("--------------\n");
	//xianxutravel(a._root);
	
	int x1, x2, y1, y2, num = 1;
	while (GetQuery(&x1, &y1, &x2, &y2))
	{
		search_x1(a._root, x1, x2, stack_x1, road_x1, 0, n);
		//取消注释可以看到路径
		//printf("road%d:= ", num);
		//for (auto i = 0; i < road_x1; i++) { printf("%d(%d) ", stack_x1[i].x, stack_x1[i].y); }
		//printf("\n");
		search_x2(a._root, x1, x2, stack_x2, road_x2, 0, n);
		//printf("road%d:= ", num++);
		//printf("%d,%d\n", road_x1, road_x2);
		//for (auto i = 0; i < road_x2; i++) { printf("%d(%d) ", stack_x2[i].x, stack_x2[i].y); }
		//printf("\n");
		int t1 = road_x1, t2 = road_x2;
		if (road_x1&&road_x2)
		{
			range_node*v = common_root();
			//取消注释可以看到公共节点
			//printf("%d,%d\n", road_x1, road_x2);
			//printf("v= %d(%d)\n", v->data.x, v->data.y
				road_x1--;
				travelReport(x1,x2,y1, y2);
			//printf("count = %d\n", count);
			if (count != 0) {
				Response(record / count);
				//取消注释可以直接看到输出
				//printf("%d\n", record / count);
				//printf("count= %d\n", count);
			}
			else {
				Response(0);
				//printf("0\n");
			}
		}
		else {
			Response(0);
			//printf("0\n");
		}
		for (auto i = 0; i < t1; i++) { stack_x1[i].c = NULL; stack_x1[i].road = NULL; stack_x1[i].x = 0; stack_x1[i].y = 0; stack_x1[i].temp = 0; }
		for (auto i = 0; i <t2; i++) { stack_x2[i].c = NULL; stack_x1[i].road = NULL; stack_x2[i].x = 0; stack_x2[i].y = 0; stack_x2[i].temp = 0; }
		t1 = t2 = road_x1 = road_x2 = record = count = 0;
	}
}

然后是temperature.in的内容

13 6
1	0	1000
3	0	1300
2	0	1600
-5	0	1100
-8	0	1200
0	0	2300
3	4	2212
4	4	3209
-4	2	1234
-1	4	1223
0	8	3212
0	3	2332
-2147483648 2147483647 1236
-8 0 6 0
-6 0 4 2
4 2 23 123
3 2 12 12
-1 9 2 10
-2147483648 -2147483648 2147483647 2147483647

最后附上100分的图。

清华数据结构平均气温AC100

我真的,搞了好久,才做出这题QAQ。附注,kd-tree不能解决该题,因为时间复杂度为清华数据结构平均气温AC100,太长了。。。