数据结构与算法实验2020夏第二批（中国石油大学） PA8题解报告——平均气温(Temperature)

目录

题目描述题目分析编码实现

一、题目描述

1. 题目描述

某气象台每天都要从遍布于各地的观察站采集气温数据，并通过互联网为远程用户提供统计查询服务。其中最常见的一类查询是，根据用户指定矩形区域内所有观察站的观测值计算出平均气温。随着更多观察站的不断建立，原始数据本身的规模急剧膨胀。另外，尽管可以假设每天采集的数据相对固定，但随着用户群体的扩大，查询的频率也日益激增。鉴于传统蛮力算法的效率已无法满足实用要求，气象台只好请你帮忙，通过改进数据结构和算法，提高查询的效率。 借助气象台提供的一组函数接口，服务器端可访问已采集到的所有数据，并报告查询结果。

2. 接口说明

int GetNumOfStation(void);

该函数必须首先调用，返回现有观察站的总数n。

void GetStationInfo(int no, int *x, int *y, int *temp);

获得第no个（0 ≤ no < n）观察站的信息：其地理坐标(*x,y)及其所测温度值temp。各观测站的测量精度统一以0.01℃为基准单位，比如12.34℃表示为整数1234。

int GetQuery(int *x1, int *y1, int *x2, int *y2);

接收下一查询请求。返回值1对应于一次有效的查询。矩阵区域的四边分别与x或y轴平行，(*x1,*y1)和(*x2,*y2)分别为其西南角和东北角的坐标。恰好被矩形边界穿过的观察站，也视作落在其中。若返回0，则表示没有更多的查询，你的程序可以退出。

void Response(int temp);

针对当前的查询，在计算出对应的平均气温后，你可通过这一接口报告所得数值(截断取整，比如12.345℃输出为1234，-12.345℃输出为-1234)。 特别注意：每调用GetQuery()接收一次查询后，若未能通过Response()函数报告该次查询的结果就再次调用GetQuery()接收下一查询，则将因为前次查询的结果无法报告而注定输出错误。也就是说，GetQuery()和Response()必须交替调用，各n次。

3. 测试说明

为便于你调试和测试，随题还附带有temperature.h和temperature_lib.c文件。前者约定了上述接口，后者是这组接口的一种实现——OJ上的实现与之不同，但接口完全一致。调试时可将它们与你的代码一同编译，但在线测试时不必提交；即便提交，OJ也会自动忽略它们。 temperature.h

#ifndef _TEMPERATURE_H_ #ifdef __cplusplus extern "C" { #endif int GetNumOfStation(void); void GetStationInfo(int no, int *x, int *y, int *temp); int GetQuery(int *x1, int *y1, int *x2, int *y2); void Response(int temp); #ifdef __cplusplus } #endif #endif //_TEMPERATURE_H_

temperature_lib.c

#include <stdio.h> #include "temperature.h" typedef struct _station_type { int x, y; int temp; } station_type; static FILE * fr = NULL; static FILE * fw = NULL; static int n, m; static int last_response, query_index; static station_type stations[50000]; extern int GetNumOfStation(void) { int i; fr = fopen("temperature.in", "r"); fw = fopen("temperature.out", "w"); fscanf(fr, "%d %d", &n, &m); for (i = 0; i < n; i++) fscanf(fr, "%d %d %d", &stations[i].x, &stations[i].y, &stations[i].temp); query_index = 0; last_response = 0; return n; } extern void GetStationInfo(int no, int *x, int *y, int *temp) { *x = stations[no].x; *y = stations[no].y; *temp = stations[no].temp; } extern int GetQuery(int *x1, int *y1, int *x2, int *y2) { if (query_index < m) { fscanf(fr, "%d %d %d %d", x1, y1, x2, y2); query_index++; return 1; } else return 0; } extern void Response(int temp) { if (last_response > query_index) fprintf(fw, "No Query\n"); for (last_response++; last_response < query_index; last_response++) fprintf(fw, "Missing\n"); fprintf(fw, "%d\n", temp); if (query_index == m) { fclose(fr); fclose(fw); } }

4. 输入

脱机调试时，temperature_lib.c所实现的三个输入接口，实际上是从当前目录下的temperature.in文件读入数据，因此通过按如下格式更改该文件，即可设定不同的输入数据：

第一行为两个整数：观察站总数n，所需查询的总次数m 以下n行分别描述各观察站：位置坐标为整数(x, y)，该站所测得温度值为整数t 再以下m行分别对应于各次查询操作，整数(x1, y1)和(x2, y2)分别表示其西南角和东北角

5. 输出

脱机调试时，temperature_lib.c所实现的Response()接口会在程序运行后，将所有的输出结果写入temperature.out文件。 文件共m行，各含1个整数，表示每次查询所得平均温度。 若查询区域不含任何观测站，则输出0。

6. 例

//输入 4 2 0 0 1000 1 1 1300 2 2 1600 3 3 1100 0 0 1 1 0 0 10 10 //输出 1150 1250

7. 限制

0 ≤n ≤ 50,000 0 ≤ m ≤ 500,000 观测站坐标取值范围是[-2^31, 2^31) 查询区域的坐标 x1 ≤ x2 且 y1 ≤ y2 时间限制：10秒 内存限制：256 MB

6. 提示

温度计算请使用64位整数，以保证累加不致溢出 kd-tree range tree

二、题目分析

代码实现

使用kd树，一层按x排序，一层按y排序，构造一个可以二维查询的树。

复杂度分析：

时间复杂度：$O(mlogn)$空间复杂度：$O(nlogn)$

三、编码实现

说明： 下述代码全部为【数据结构与算法实验 OJ 平台】提交过的代码。

#include "cstdio" #include "stdlib.h" #include "temperature.h" using namespace std; long long int val1, val2, las; struct Node1 { int data[2]; int max[2]; int min[2]; int v, l, r; long long int sum, cnt; int &operator[](int x) { return data[x]; } friend bool operator==(Node1 a, Node1 b) { return a.data[0] == b.data[0] && a.data[1] == b.data[1]; } friend bool operator<(Node1 a, Node1 b) { return a[val2] < b[val2]; } } p[200005]; struct Node2 { Node1 temperatureList[200005]; Node1 current; int rt; int cnt; long long int count, ans; void NodeUpdate(int); void NodeUpdate(int &, bool); void NodeUpdate(int, int, int, int, int); int NodeUpdate(int, int, bool); } T; int CMP(const void *, const void *); bool Insert(int, int, int, int, int, int, int, int); bool Outter(int, int, int, int, int, int, int, int); inline int getMax(int, int); inline int getMin(int, int); int main() { val1 = GetNumOfStation(); if (val1 == 0) { int x1, x2, y1, y2; while (GetQuery(&x1, &y1, &x2, &y2)) { Response(0); printf("0\val1"); } return 0; } int x, y, x2, y2; for (int i = 0; i < val1; i++) { GetStationInfo(i, &p[i + 1][0], &p[i + 1][1], &p[i + 1].v); p[i + 1].sum = p[i + 1].v; } T.rt = T.NodeUpdate(1, val1, 0); while (GetQuery(&x, &y, &x2, &y2)) { T.count = 0; T.ans = 0; T.NodeUpdate(T.rt, x, y, x2, y2); if (T.count != 0) { Response(T.ans / T.count); } else { Response(0); } } return 0; } int CMP(const void *x, const void *y) { return (*(Node1 *)y)[val2] - (*(Node1 *)x)[val2]; } bool Insert(int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2) { return x1 <= X1 && X2 <= x2 && y1 <= Y1 && Y2 <= y2; } bool Outter(int x1, int y1, int x2, int y2, int X1, int Y1, int X2, int Y2) { return x1 > X2 || x2 < X1 || y1 > Y2 || y2 < Y1; } inline int getMax(int a, int b) { return (a > b ? a : b); } inline int getMin(int a, int b) { return (a < b ? a : b); } void Node2::NodeUpdate(int k) { int l = temperatureList[k].l, r = temperatureList[k].r; for (int i = 0; i < 2; i++) { temperatureList[k].min[i] = temperatureList[k].max[i] = temperatureList[k][i]; if (l) temperatureList[k].min[i] = getMin(temperatureList[k].min[i], temperatureList[l].min[i]); if (l) temperatureList[k].max[i] = getMax(temperatureList[k].max[i], temperatureList[l].max[i]); if (r) temperatureList[k].min[i] = getMin(temperatureList[k].min[i], temperatureList[r].min[i]); if (r) temperatureList[k].max[i] = getMax(temperatureList[k].max[i], temperatureList[r].max[i]); } temperatureList[k].sum = temperatureList[k].v + temperatureList[l].sum + temperatureList[r].sum; temperatureList[k].cnt = 1 + temperatureList[l].cnt + temperatureList[r].cnt; } void Node2::NodeUpdate(int &k, bool val2) { if (!k) { k = ++cnt; temperatureList[k][0] = temperatureList[k].min[0] = temperatureList[k].max[0] = current[0]; temperatureList[k][1] = temperatureList[k].min[1] = temperatureList[k].max[1] = current[1]; } if (current == temperatureList[k]) { temperatureList[k].v += current.v, temperatureList[k].sum += current.v; return; } if (current[val2] < temperatureList[k][val2]) NodeUpdate(temperatureList[k].l, val2 ^ 1); else NodeUpdate(temperatureList[k].r, val2 ^ 1); NodeUpdate(k); } void Node2::NodeUpdate(int k, int x1, int y1, int x2, int y2) { if (k == false) { return; } if (Insert(x1, y1, x2, y2, temperatureList[k].min[0], temperatureList[k].min[1], temperatureList[k].max[0], temperatureList[k].max[1]) == true) { ans += temperatureList[k].sum; count += temperatureList[k].cnt; return; } if (Outter(x1, y1, x2, y2, temperatureList[k].min[0], temperatureList[k].min[1], temperatureList[k].max[0], temperatureList[k].max[1]) == true) { return; } if (Insert(x1, y1, x2, y2, temperatureList[k][0], temperatureList[k][1], temperatureList[k][0], temperatureList[k][1]) == true) { ans += temperatureList[k].v; count++; } NodeUpdate(temperatureList[k].l, x1, y1, x2, y2); NodeUpdate(temperatureList[k].r, x1, y1, x2, y2); } int Node2::NodeUpdate(int l, int r, bool f) { if (l > r) { return 0; } int temp = (l + r) >> 1; val2 = f; qsort(p + l, r - l + 1, sizeof(p[0]), CMP); temperatureList[temp] = p[temp]; temperatureList[temp].l = NodeUpdate(l, temp - 1, f ^ 1); temperatureList[temp].r = NodeUpdate(temp + 1, r, f ^ 1); NodeUpdate(temp); return temp; }