题意分析

题目描述了一个水箱，水箱的尺寸为100cm（宽）×50cm（高）×30cm（深）。水箱内部有若干块隔板，隔板平行于水箱的侧板，宽度为30cm（即与水箱深度相同），高度各不相同且小于50cm。水箱上方有多个水龙头，每个水龙头以一定的流量向水箱中注水。初始时水箱为空，水龙头在实验开始时打开。需要模拟水箱中水位的上升过程，并在给定的时间和位置输出水位的高度。

1.输入格式 第一行是数据集的数目D。

每个数据集包含：

隔板的数量N，以及每个隔板的位置Bi和高度Hi。

水龙头的数量M，以及每个水龙头的位置Fj和流量Aj。

观测次数L，以及每次观测的位置Pk和时间Tk。

2.输出格式 对于每个观测点Pk和时间Tk，输出水位高度，保留3位小数。

解题思路

1.初始化水箱结构：

根据输入的隔板信息，将水箱分成多个区域（区间）。每个区间的左右边界由隔板或水箱的侧板决定，区间的高度由左右隔板的高度决定。

2.水龙头分配：

将每个水龙头的流量分配到对应的区间中。水龙头的位置决定了它属于哪个区间。

3.事件处理：

使用优先队列（最小堆）来处理事件。事件包括：

水位计算事件（Height_calc）：在给定的时间和位置计算水位高度。

区间满水事件（Water_full）：某个区间的水位达到其最大高度（即左右隔板的最小高度），此时需要合并相邻的满水区间，并重新分配水流。

4。水位上升模拟：

对于每个区间，根据其当前的水流量和水位高度，计算水位上升的速度。

当某个区间的水位达到其最大高度时，触发区间满水事件，处理合并和重新分配水流。

在每次水位计算事件时，根据当前的水位和剩余时间，计算水位高度。

5.关键点 区间合并：当一个区间的水位达到其最大高度时，需要检查是否可以与相邻的满水区间合并，形成更大的满水区间。

水流重新分配：合并后的区间需要重新分配水流，可能将水流分配到相邻的未满区间。

事件优先级：使用优先队列确保事件按时间顺序处理，优先处理时间早的事件。

代码实现

#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

enum Type{
	IN,
	LEFT,
	RIGHT,
	DOUBLE,
};

enum Event{
	Water_full,
	Height_calc,
};

struct Info{
	void set(double arg_left_H, double arg_right_H, double arg_left_X, double arg_right_X, double arg_per_water, double arg_water_height){
		left_H = arg_left_H;
		right_H = arg_right_H;
		left_X = arg_left_X;
		right_X = arg_right_X;
		per_water = arg_per_water;
		water_height = arg_water_height;
	}
	
	double left_H, right_H, left_X, right_X, per_water, water_height;
	Type type;
};

struct Data{
	Data(double arg_time, double arg_LOC, int arg_id, Event arg_event){
		time = arg_time;
		LOC = arg_LOC;
		id = arg_id;
		event = arg_event;
	}
	bool operator<(const struct Data &arg) const{
		return time > arg.time; 
	}
	double time, LOC;
	int id;
	Event event;
};

Info info[11], next_info[11];
double in_water[11];

void func(){
	
	int N;
	scanf("%d", &N);
	
	for(int i = 0; i <= N; i++){
		info[i].per_water = 0.0;
		info[i].water_height = 0;
		info[i].type = IN;
	}
	
	double X, height;
	info[0].left_X = 0;
	info[0].left_H = 50.0;
	
	for(int i = 1; i <= N; i++){
		scanf("%lf %lf", &X, &height);
		info[i-1].right_X = X;
		info[i-1].right_H = height;
		info[i].left_X = X;
		info[i].left_H = height;
	}
	info[N].right_X = 100.0;
	info[N].right_H = 50.0;
	N++;
	
	int M;
	scanf("%d", &M);
	
	double water;
	for(int loop = 0; loop < M; loop++){
		scanf("%lf %lf", &X, &water);
		for(int i = 0; i < N; i++){
			if(X > info[i].left_X && X < info[i].right_X){
				info[i].per_water += water;
				break;
			}
		}
	}
	
	for(int i = 0; i < N; i++) in_water[i] = info[i].per_water;
	
	int L;
	scanf("%d", &L);
	
	priority_queue<Data> Q;
	double tmp_time;
	for(int loop = 0; loop < L; loop++){
		scanf("%lf %lf", &X, &tmp_time);
		Q.push(Data(tmp_time, X, loop, Height_calc));
	}
	
	double min_time = DBL_MAX;
	int min_id;
	for(int i = 0; i < N; i++){
		tmp_time = (info[i].right_X - info[i].left_X) * min(info[i].left_H, info[i].right_H) * 30.0 / info[i].per_water;
		if(tmp_time < min_time){
			min_time = tmp_time;
			min_id = i;
		}
	}
	
	Q.push(Data(min_time, -1, min_id, Water_full));
	double pre_calc_height_time = 0; 
	double add_water, add_height, pre_height, new_per_water;
	int id, count = 0, left_id, right_id, next_info_index;
	int merge_left, merge_right;
	
	double ans[10];
	
	while(!Q.empty()){
		
		if(Q.top().event == Height_calc){
			
			for(int i = 0; i < N; i++){
				if(Q.top().LOC > info[i].left_X && Q.top().LOC < info[i].right_X){
					id = i;
					break;
				}
			}
			
			if(info[id].type == IN){ 
				
				add_water = in_water[id] * (Q.top().time - pre_calc_height_time);
				add_height = add_water / ((info[id].right_X - info[id].left_X) * 30.0);
				
				ans[Q.top().id] = info[id].water_height + add_height;
				
			} else { 
				ans[Q.top().id] = info[id].water_height;
			}
			count++;
			if(count == L){
				for(int k = 0; k < L; k++){
					printf("%.3f\n", ans[k]);
				}
				return;
			}
			
		} else { 
			
			for(int i = 0; i < N; i++){
				if(info[i].type != IN) continue; 
				add_water = in_water[i] * (Q.top().time - pre_calc_height_time);
				add_height = add_water / ((info[i].right_X - info[i].left_X) * 30.0);
				info[i].water_height += add_height;
			}
			pre_calc_height_time = Q.top().time;
			
			id = Q.top().id;
			merge_left = id;
			merge_right = id;
			
			if(id > 0 && info[id-1].type != IN && fabs(info[id-1].water_height - info[id].water_height) < EPS){
				merge_left = id-1;
			}
			
			if(id+1 < N && info[id+1].type != IN && fabs(info[id+1].water_height - info[id].water_height) < EPS){
				merge_right = id+1;
			}
			
			new_per_water = 0;
			for(int i = merge_left; i <= merge_right; i++){
				new_per_water += info[i].per_water;
			}
			
			next_info_index = 0;
			
			for(int i = 0; i < merge_left; i++){
				next_info[next_info_index++] = info[i];
			}
			next_info[next_info_index].set(info[merge_left].left_H, info[merge_right].right_H, info[merge_left].left_X, info[merge_right].right_X,
				new_per_water, info[merge_left].water_height);
			next_info[next_info_index].type = DOUBLE; 
			next_info_index++;
			for(int i = merge_right+1; i < N; i++){
				next_info[next_info_index++] = info[i];
			}
			
			N = next_info_index;
			for(int i = 0; i < N; i++){
				info[i] = next_info[i];
			}
			
			for(int i = 0; i < N; i++) in_water[i] = 0;
			
			for(int i = 0; i < N; i++){
				if(info[i].water_height + EPS < min(info[i].left_H, info[i].right_H)){
					info[i].type = IN;
					in_water[i] += info[i].per_water;
					continue;
				}
				
				id = i;
				left_id = id;
				
				left_id = id;
				pre_height = info[id].water_height;
				while(left_id > 0 && info[left_id-1].water_height < pre_height && info[left_id-1].right_H <= pre_height + EPS){
					left_id--;
					pre_height = info[left_id].water_height;
					if(info[left_id].type == IN) break;
				}
				
				right_id = id;
				pre_height = info[id].water_height;
				while(right_id+1 < N && info[right_id+1].water_height < pre_height && info[right_id+1].left_H <= pre_height + EPS){
					right_id++;
					pre_height = info[right_id].water_height;
					if(info[right_id].type == IN) break;
				}
				
				if(left_id == id){ 
					
					if(right_id == id){
						info[i].type = DOUBLE; 
					} else {
						info[i].type = RIGHT;
						in_water[right_id] += info[i].per_water;
					}
					
				} else {
					
					if(right_id == id){ 
						info[i].type = LEFT;
						in_water[left_id] += info[i].per_water;
					} else { 
						info[i].type = DOUBLE;
						in_water[left_id] += info[i].per_water / 2;
						in_water[right_id] += info[i].per_water / 2;
					}
				}
			}
			
			min_time = DBL_MAX;
			for(int i = 0; i < N; i++){
				if(info[i].type != IN) continue;
				tmp_time = (info[i].right_X - info[i].left_X) * (min(info[i].left_H, info[i].right_H) - info[i].water_height) * 30.0 / in_water[i];
				if(tmp_time < min_time){
					min_time = tmp_time;
					min_id = i;
				}
			}
			
			Q.push(Data(Q.top().time + min_time, -1, min_id, Water_full));
			
		}
		Q.pop();
	}
}

int main(){
	
	int D;
	scanf("%d", &D);
	
	for(int loop = 0; loop < D; loop++){
		func();
	}
	
	return 0;
}