本文主要是介绍蓝桥杯刷题day13——乘飞机【算法赛】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、问题描述
等待登机的你看着眼前有老有小长长的队伍十分无聊，你突然想要知道，是否存在两个年龄相仿的乘客。每个乘客的年龄用一个 0 到 36500 的整数表示，两个乘客的年龄相差 365 以内就认为是相仿的。
具体来说，你有一个长度为 n 的数组，每个数组元素都是一个 0∼36500 的整数。给出 q 个二元组 l,r，判断数组在区间 [l,r] 上是否存在两个差值小于等于 365 的数，若存在输出 YES，否则输出 NO。
输入格式
第一行两个整数 n,q，表示乘客数和询问数。
接下来一行 n 个整数，表示乘客的年龄。
接下来 q 行，每行两个整数 l,r 表示查询。
输出格式
q 行，每行输出 YES 或者 NO，分别表示区间内存在/不存在年龄相仿的乘客。
样例输入
6 3
20 800 400 175 146 456
1 3
1 4
1 6
样例输出
NO
YES
YES
说明
对于区间 [1,3]，最小相邻为 400−20=380>365。
二、解析
这个问题可以通过遍历每个查询区间来解决。对于每个查询区间，我们需要检查区间内是否存在两个年龄相差不超过365的乘客。这里有两个关键点：
-
如果查询区间的长度本身就很大（大于或等于整个年龄范围
36500//365，即100），那么显然区间内至少存在两个年龄相差不超过365的乘客，因此可以直接输出"YES"。 -
如果查询区间的长度较小，我们需要对区间内的年龄进行排序，然后遍历排序后的列表，检查相邻年龄之间的差值。如果存在差值小于等于365的情况，即输出"YES"。如果遍历完整个列表都没有找到这样的差值，则输出"NO"。
三、python代码
n,q=map(int,input().split())
age_ls=list(map(int,input().split()))
q_ls=[]
for i in range(q):a,b=map(int,input().split())q_ls.append([a-1,b-1])for i in range(q):l,r=q_ls[i]if r-l>=36500//365:print("YES")else:new_ls=sorted(age_ls[l:r + 1])for i in range(r-l):if new_ls[i+1]-new_ls[i]<=365:print("YES")breakelse:print("NO")四、运行结果
这篇关于蓝桥杯刷题day13——乘飞机【算法赛】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
