蓝桥杯1944: 蓝桥杯算法提高VIP-Air Traffic Control题解

凌晚轩 算法基础篇 52 0
全网最全C++题库,助您快速提升编程技能!题库丰富多样,涵盖各个领域,让您在练习中不断成长!
在任意时刻,每一个控制中心都有一个圆形“控制范围”,其半径等于其所监控的最远的那架飞机的距离,所有在控制范围内的飞机都被该控制中心监控,但是在控制范围边界上的飞机可能或可能不被控制中心监控,这取决于控制中心的容量和以上列出的优先级。

为了避免空中相撞,大部分商业航班都被地面航空管制中心使用雷达跟踪其位置来监控。在这个问题中,你会被给予一组飞机和一组控制中心的信息,并计算出飞机是如何被控制中心监控的(这句话的意思参考输入描述:即计算恰好被K个控制中心监控的飞机数目),飞机的位置用(x,y)坐标表示,基于此题的目的,无视飞机的高度(海拔)。 一个给定的控制中心能够监控的飞机数量因设备和工作人员的改变而时刻变化。在任一时刻,每一个控制中心会尽可能地监控更多的飞机,它会按照如下优先级选择其监控的飞机:1.离这个控制中心欧几里得距离比较近的优于比较远的。2.若两架飞机到控制中心的距离相同,那么选择其中往北更远的(y坐标轴正方向)。3.如果两架飞机的距离和y坐标都相同,优先选择往东更远的(x坐标正方向)。(补充说明:也就是说在距离相同的情况下,先比较y坐标,y坐标大的优先级高,若y坐标依旧相同,x坐标大的优先级高。数据会保证没有任意两个飞机的坐标相同。) 在任意时刻,每一个控制中心都有一个圆形“控制范围”,其半径等于其所监控的最远的那架飞机的距离。所有在控制范围内的飞机都被该控制中心监控,但是在控制范围边界上的飞机可能或可能不被控制中心监控,这取决于控制中心的容量和以上列出的优先级。 你不会被告知控制中心的位置,取而代之的,对于每个控制中心,你会被告知它当前监控的飞机个数,以及其监控范围边界上的两点,用这些信息,你能计算出控制中心的位置,以及决定哪些飞机被其监控。如果数据包含多种可能的监控范围,你应该选择包含了靠北最远的那架飞机的,通过先选择靠北最远的再选择靠东最远的打破平局(——这段话的意思你可以这么认为:如果有多种可能的控制范围以及对应的控制中心位置满足输入要求,那么我们这么来判定:将飞机按照y坐标从大到小,y坐标相同的按照x从大到小排序,然后依次考虑,如果有架飞机在控制范围A内,而其不在控制范围B内,则我们会选择A而不是B。注意,若两个控制范围监控的飞机的集合相同,可以任意选择一个,因为这不影响答案)。 下面这张图展示了两个控制中心和四架飞机的情况。每个控制中心用一个圆形控制区域和这个区域中的两个点表示,用A和B标记。P1,P2,P3,P4标记了四架飞机。在这个例子中,飞机P1和P4都被一个单独的控制中心监视,而P3被两个控制中心监控,但P2却没有被任何一个控制中心监控。

蓝桥杯1944: 蓝桥杯算法提高VIP-Air Traffic Control题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
不断挑战自我,才能突破极限!全网最全C++题库,让您在编程道路上越走越远。

标签: 蓝桥杯1944: 蓝桥杯算法提高VIP-Air Traffic Control题解