1.题目

image-20231205211211007 image-20231205211317985

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。

    接下来，我们进行如下操作：

    1. 如果a[l]+a[r]>Z, 说明当前下标对不满足条件，我们需要减小 ai+a; 的值，而数组已经有序，所以我们

    将 r 减 一 ，即γ –。

    1. 如果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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
long long arr[N];


int getNUmber(int len,int val) {
    ll l = 1;
    ll r = len;
    long long  num = 0;
    while(l < r) {
        while(l < r and arr[l] + arr[r] > val) {
            r--;
        }
        num += r - l;
        l++;
    }

    return num;
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,L,R;
    cin >> n >> L >> R;

    for(int i = 1;i <= n;++i) {
        cin >> arr[i];
    }

    sort(arr + 1,arr + 1 + n);
    // 1.设本题 <= R的组合有 y 个
    // 2.设本题 <= L - 1的元素有 x个
    // 3.即本题答案就是 y - x 个，即属于[L,R]范围内的组合对数

    cout << getNUmber(n,R) - getNUmber(n,L -1) << "\n";

    
    return 0;
}

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 就能得到 4

    1 2 3 4 5 6 7 8
    low upper 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
  ll n,L,R;
  cin>>n>>L>>R;
  vector<ll> arr(n);

  for(int i=0;i<n;++i)
  {
    cin>>arr[i];
  }
  ll cnt=0;
  sort(arr.begin(),arr.end());//将序列从小到大排序便于查找
  for(int i=0;i<n;++i)
  {
    ll left=L-arr[i],right=R-arr[i];//将L<=arr[i]+arr[j]<=R转化为L-arr[i]<=arr[j]<=R-arr[j],使用二分查找搜索arr[j]
    cnt += upper_bound(arr.begin()+i+1,arr.end(),right)-lower_bound(arr.begin()+i+1,arr.end(),left);
    //每次加上搜索到的区间长度即可
  }
  cout<<cnt<<endl;
  return 0;
}