【每日一题】YACS 243：5G通讯

题目描述

这是上海计算机学会竞赛 $P243$：5G通讯（$2020$年$9$月月赛 乙组$T2$）
标签：二分查找
题意：给定$n$个点，第$i$个点的坐标为$x_i$。给定限制$d$，如果两点距离不超过$d$，那么它们可以直接通讯，统计可以有多少对点可以直接通讯。（$1<=n<=10^5,1<=x_i,d<=10^9$）

解决方案

80 分题解：很多同学直接暴力枚举第$i$个点前有多少个点和它的坐标距离不超过$d$，这个写法也不错，并且因为是枚举第$i$个点前的，还可以避免重复的情况出现（即$(a,b)$和$（b,a）$的情况）。但是时间复杂度是$O(n^2)$，还是会超时。
80 分代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n, d, a[100005];

int main() {
   
    cin >> n >> d;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 排序 保证序列有序
    sort(a + 1, a + 1 + n);

    ll cnt = 0; // 直接通讯的点对数
    for (int i = 1; i <= n; i++) {
   
        for (int j = 1; j < i; j++) {
   
            if (a[i] - a[j] <= d) cnt++;
        }
    }

    cout << cnt;
    return 0;
}

题解：正解应该比较容易想到第二层$j$循环能不能优化，想一想这层循环的逻辑其实就是想在第$i$个数前找有多少个大于等于$a_i-d$的数。（$a_i-a_j<=d$转换成$a_i-d<=a_j$），那这一部分是不是可以用二分查找去找一下。然后简单思考一下，最极端的情况是不是有$n\ast (n-1)/2$个点对，会爆掉$int$，得开$longlong$。
代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n, d, a[100005];

int main() {
   
    cin >> n >> d;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 排序 保证序列有序
    sort(a + 1, a + 1 + n);

    ll cnt = 0; // 直接通讯的点对数
    for (int i = 1; i <= n; i++) {
   
        ll p = lower_bound(a + 1, a + 1 + n, a[i] - d) - a;
        cnt += i - p;
    }

    cout << cnt;
    return 0;
}