蓝桥杯刷题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的乘客。这里有两个关键点：

1. 如果查询区间的长度本身就很大（大于或等于整个年龄范围 36500//365，即100），那么显然区间内至少存在两个年龄相差不超过365的乘客，因此可以直接输出"YES"。

2. 如果查询区间的长度较小，我们需要对区间内的年龄进行排序，然后遍历排序后的列表，检查相邻年龄之间的差值。如果存在差值小于等于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")
                break
        else:
            print("NO")
 

四、运行结果