蓝桥杯备赛选题——聪明的小羊肖恩
1.题目
![image-20231205211211007](https://zhihuan-1302250699.cos.ap-nanjing.myqcloud.com/images/image-20231205211211007.png?imageSlim)
![image-20231205211317985](https://zhihuan-1302250699.cos.ap-nanjing.myqcloud.com/images/image-20231205211317985.png?imageSlim)
2.解法
2.1 正常思路
题目要求我们求出下标对(i,j) 使得ai+aj∈[L,R] 的下标对数量。根据简单的容斥原理可知,设ai+aj≤R
的下标对数量为y,ai+aj≤L-1 的下标对数量为 x, 则 ai+aj∈[L,R] 的下标对数量为y-x 。
问题转化为对于一个给定的数Z, 我们如何求出a 中满足ai+a;≤Z 的下标对数量。为了解决这个问题,我们可 以首先对数组a 进行排序。排序后,我们可以使用双指针技巧来遍历数组,并计算满足条件的下标对数量。我们定义
两个指针l 和 r, 分别表示数组a 中的左右元素下标。初始时, l=1,r=n。
接下来,我们进行如下操作:
- 如果a[l]+a[r]>Z, 说明当前下标对不满足条件,我们需要减小 ai+a; 的值,而数组已经有序,所以我们
将 r 减 一 ,即γ –。
- 如果a[l]+a[r]≤Z, 说明当前下标对以及之后的所有下标对都满足条件。我们需要计算满足条件的下标对数
量,可以通过r-l 计算。然后我们将l加一,即l++。
我们重复以上操作,直至l<r 不再成立。这样我们就找到了所有满足ai+aj≤Z 的下标对数量。
时间复杂度:排序的复杂度为 O(nlogn), 双指针的复杂度为 O(n), 即整体的复杂度为O(nlogn)。
可以设本题 > R 的有y个,大于 L - 1 的有 x 个
例如范围是 [4,6]
大于 ai + aj > 6 包含 6 ,7两个元素(ai默认排序后最小值,即为1,1+7或者1+6都大于6),这时 r– 到5的位置1 2 3 4 5 6 i j 当 i = 1,r =5 时,两数相加 <= R 的组合有 r - l 个,即 5 - 1 = 4。
之后i++,i变为2,从2开始向后组合,找到 ai + aj <= R的组合。
1 2 3 4 5 6 i j 很明显, 2 + 5 是 > R 的,这时循环令 r–,直到ai + aj <= R
1 2 3 4 5 6 i j 这时 2 + 4 <= R,然后里面符合 <= R的组合有 4 - 2个。
同理继续,找出所有 <= R的元素。
接下来 找出 <= L - 1的所有组合,因为 <= R的所有集合数 减去 <= L - 1的集合数,就等于 在 [L,R]的所有集合数。
找出所有 <= 3(L - 1)的集合数
j依次–,找到第一个组合小于 4 的,只有一对。1 2 3 4 5 6 i j 之后 让 <=R的集合减去 <= L - 1,的集合,就能得到结果,即L <= z <= R的元素有 z = y - x 个
代码如下:
1 |
|
2.2 大佬思路
在一个乱序的数组中查找满足条件的元素个数,首先想到将其排序以便于后续操作;
题中给出了两个限制条件:1<=i<j<=n和L<=a[i]+a[j]<=R,在排序过后第一个条件可以转化为找到两个下标不相同的元素即可,而后一个条件则变形为L-a[i]<=a[j]<=R-a[i],即对于每一个确定的a[i],满足条件的a[j]范围为[L-a[i],R-a[i] ]在此区间内使用二分查找函数进行查找,将返回的指针相减即得到区间长度,累加此长度即为最终答案。
利用了数学不等式的思想,巧妙转换为 查找 符合 aj的区间。
利用 upper_boud查找第一个 > target的元素下标地址
利用lower_bound查找第一个 >= target的元素下标地址
例如 [4,7] 包含四个元素 4,5,6,7,利用upper - low 就能得到 41 2 3 4 5 6 7 8 low upper
1 |
|