如何快速进行网站开发,服务平台登录入口官网,哈尔滨设计优化公司,wordpress 黑色文章目录 会议室预约系统优化问题描述差分 会议室预约系统优化
问题描述
假设你是一家大型企业的 IT 工程师#xff0c;企业内有
n 个会议室#xff0c;每天都有多个部门预约会议室进行会议。你的任务是优化现有的会议室预约系统。
你需要设计一个程序来支持以下两种操作… 文章目录 会议室预约系统优化问题描述差分 会议室预约系统优化
问题描述
假设你是一家大型企业的 IT 工程师企业内有
n 个会议室每天都有多个部门预约会议室进行会议。你的任务是优化现有的会议室预约系统。
你需要设计一个程序来支持以下两种操作
预约会议室: 给定一个时间范围 [start,end] 和一个会议室的 ID 预约该会议室在这个时间范围内。查询会议室状态: 给定一个时间点 t 和一个会议室的 ID返回该会议室在时间点 t 的预约状态即在这个时间点该会议室正在被预约多少次。
输入格式 第一行包含一个整数 n表示会议室的数量。
第二行包含一个整数 q表示操作的数量。
接下来 q 行每行描述一个操作。
如果是预约操作则格式为BOOK starttime endtime roomid。
如果是查询操作则格式为QUERY t roomid。
输出格式 对于每一个 QUERY 操作输出一个整数表示到时间点 t 为止该会议室被预约了多少次。
样例输入
3
5
BOOK 10 20 0
BOOK 15 25 1
BOOK 20 30 0
QUERY 15 0
QUERY 25 1样例输出
1
0这里蓝桥官方给的样例好像是错的应该为
1
1评测数据范围 1≤n≤1051≤q≤105 0≤starttimeendtime≤109 0≤t≤109 。
差分
#includebits/stdc.h
using namespace std;int main()
{int n,q; // n是会议室的数量q是操作的数量。scanf(%d %d,n,q); // 读取n和q的值。vectormapint,int a(n); // 创建一个向量a包含n个map每个map用于存储每个会议室的预约开始时间和结束时间的差分。while(q--) // 遍历q次操作。{string s;cins; // 读取操作的类型BOOK或QUERY。if(sBOOK){int l,r,id; // l为预约开始时间r为预约结束时间id为会议室的ID。scanf(%d %d %d,l,r,id); // 读取这三个值。a[id][l]1; // 在预约开始时间增加一个预约。a[id][r1]-1; // 在预约结束时间的下一时刻减少一个预约。}else{int t,id; // t是查询的时间点id是会议室的ID。scanf(%d %d,t,id); // 读取这两个值。int cnt0; // cnt用于统计到时间点t该会议室的预约总次数。for(auto i : a[id]) // 遍历id会议室的所有预约记录。{if(i.first t) break; // 如果记录的时间点大于查询时间点t则结束循环。cnt i.second; // 累加每个有效时间点的预约差分值。}printf(%d\n,cnt); // 输出到时间点t会议室id的预约总次数。}}return 0;
}这个代码使用了一种称作差分数组的技术来高效管理会议室预约的增加和减少。通过在预约开始时增加计数在预约结束后的下一时刻减少计数这样就可以通过累加到任何给定时间点的差分值来计算该时间点的总预约次数。这种方法的优点是更新预约状态的操作时间复杂度为O(1)查询操作的时间复杂度为O(m)其中m是对应会议室的预约记录条数这在大多数情况下要优于直接遍历每个预约记录来计算总预约次数。
