题解 | #万万没想到之抓捕孔连顺#

题目的要求是相距最远的2个人距离不超过d，所以当我们确定了距离最远的2个人的距离，那么第3个人的坐标就是在这2人之间进行排列组合。所以问题就转化为给定一有序数组a，对于a中的每一个元素查找出距离最大且小于d的另一个元素

普通直接遍历会超时因为数组有序，可以用二分查找或者滑动窗口（记得开long long）：

1.二分查找：

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

int v[1000005];
//二分查找
ll b_s(ll l,ll r,ll target){
    ll res = r;
    while(l <= r){
        ll mid = (l+r)/2;
        if(v[mid] >= target){     //check条件是判断是否满足，满足就暂时记下来
            res = mid;
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    return res;
}

const ll mod = 99997867;
！
int main(){
    ll n,d;  cin >> n >> d;
    for(ll i=0;i<n;i++){
        cin >> v[i];
    }
    ll ans = 0;
    for(ll i=0;i<n;i++){
        ll a = v[i];
        ll j;
        if(v[n-1] <= a+d){
            j = n-1;
        }else{
            j=b_s(i,n-1,a+d);
            if(v[j] > a+d){
                j--;
            }
        }
        ll x = j-1-i;
        ans += (x*(x+1)/2)%mod;
        ans = ans%mod;
    }
    cout << ans;
    return 0;
}

滑动窗口，指针不回溯：

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

//滑动窗口
const ll mod = 99997867;
int main(){
    ll n,d;  cin >> n >> d;
    ll v[n];
    for(ll i=0;i<n;i++){
        cin >> v[i];
    }
    ll ans = 0,j=0;
    for(ll i=0;i<n;i++){
        while(v[j] - v[i] <= d && j <= n-1){
            j++;
        }
        ll x = j-1-i-1;
        ans += x*(x+1)/2;
        ans = ans%mod;
    }
    cout << ans;
    return 0;
}