学做网站需要多少钱,网站建设所要花费的资金,东莞网站建设上科,海南在线天涯论坛一、问题描述
等待登机的你看着眼前有老有小长长的队伍十分无聊#xff0c;你突然想要知道#xff0c;是否存在两个年龄相仿的乘客。每个乘客的年龄用一个 0 到 36500 的整数表示#xff0c;两个乘客的年龄相差 365 以内就认为是相仿的。 具体来说#xff0c;你有一个长度…一、问题描述
等待登机的你看着眼前有老有小长长的队伍十分无聊你突然想要知道是否存在两个年龄相仿的乘客。每个乘客的年龄用一个 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−20380365。
二、解析
这个问题可以通过遍历每个查询区间来解决。对于每个查询区间我们需要检查区间内是否存在两个年龄相差不超过365的乘客。这里有两个关键点 如果查询区间的长度本身就很大大于或等于整个年龄范围 36500//365即100那么显然区间内至少存在两个年龄相差不超过365的乘客因此可以直接输出YES。 如果查询区间的长度较小我们需要对区间内的年龄进行排序然后遍历排序后的列表检查相邻年龄之间的差值。如果存在差值小于等于365的情况即输出YES。如果遍历完整个列表都没有找到这样的差值则输出NO。
三、python代码
n,qmap(int,input().split())
age_lslist(map(int,input().split()))
q_ls[]
for i in range(q):a,bmap(int,input().split())q_ls.append([a-1,b-1])for i in range(q):l,rq_ls[i]if r-l36500//365:print(YES)else:new_lssorted(age_ls[l:r 1])for i in range(r-l):if new_ls[i1]-new_ls[i]365:print(YES)breakelse:print(NO)
四、运行结果
