由于题目数据大，O(n^2)明显会爆，所以用二分

#include <bits/stdc++.h>
using namespace std;
long long n,k,a[500001],sum,l,r,mid,ans;
int main(){
	cin>>n>>k;
	for (long long i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);//升序排序 
	for (long long i=1;i<=n;i++){
		l=i;
		r=n;
		ans=0;
		while(l<=r){
			mid=(l+r)/2;
			if (a[mid]>=a[i]+k){//条件 
				r=mid-1;
				ans=mid;
			}
			else{
				l=mid+1;
			}
		}
		if (ans!=0){//ans不为0，就代表有那个数 
			sum+=n-ans+1;
		}
	}
	cout<<sum;
	return 0;
}

60分做法（剩余40分均TLE，非WA）
暴力搜索

    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(abs(a[i]-a[j])>=k){
                ans++;
            }
        }
    }

90分做法（剩余10分为TLE）
优化后的暴搜

int n,k,a[500005],x=2;
long long ans;
    ······
    sort(a+1,a+n+1);
    for(int i=1;i<n;i++){
        for(int j=x;j<=n;j++){
            if(abs(a[i]-a[j])>=k){
                ans+=n-j+1;
                x=j;
                break;
            }
        }
    }
    ······

主要就加了个sort，然后因为从小到大，所以当找到第一个abs(a[i]-a[j])>=k的位置就说明后面的全部数据都符合条件，那就不用再往后遍历了。


100分做法
使用lower_bound函数

#include<bits/stdc++.h>
using namespace std;
int n,k,a[500005];
long long ans;
int main(){
    ios::sync_with_stdio(false); // O2优化
    cin.tie(0); // 输入加速
    cout.tie(0); // 输出加速
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1); // 升序排序
    for(int i=1;i<n;i++){
        ans+=n-(lower_bound(a+i,a+n+1,a[i]+k)-(a+1)); // 说明下面补↓
    }
    cout<<ans;
    return 0;
}

众所周知指针属于C++中最难掌握的内容没有之一，指针中存储的是一个地址而非具体的值。
一般我们在程序中进行运算时，操作的都是对象的值，而非地址。我们在遍历数组时也是如此。
虽然直接操作值很方便，但是效率是低于操作指针的。
lower_bound函数的返回值就是一个指针，所以函数外面要减去(a+1)，a是数组，如果cout<<a; 实际上是输出a的地址，所以a也是个类似指针的玩意儿，因此函数外减去(a+1)就相当于抵消了返回的指针类型，变成了一个确定的值。至于为什么是减去(a+1)而不是减去a，这是因为在我的这个程序中，数组的起始位置（有意义的下标）是1而不是0，如果是0的话就要减去a，同样的如果是10的话就要减去(a+10)
90分做法就是因为操作的不是指针，所以运算速度慢了，导致最后一个样例过不了，而操作指针就避免的这个问题，轻轻松松过样例。
使用这个函数前的10个样例总耗时≥1419ms，使用这个函数之后的总耗时仅868ms，减少了将近1/2。

约400ms

#include <cstdio>
#include <algorithm>
using namespace std;
int n , k , a[500005] ;
long long ans;
//不用加速输入输出了，直接快读
inline int reader(){
	int out = 0 , chr = getchar();
	while('0' > chr || chr > '9')
		chr = getchar() ;
	while('0' <= chr && chr <= '9')
		out += out * 9 + chr - '0' ,chr = getchar() ;
	return out ;
} 
int main(){
	n = reader() ;//读取
	k = reader() ;
	for(int i = 0 ; i < n ; i ++)
		a[i] = reader() ;
	sort(a , a + n) ;//排序
	int j = 0 ; 
	for(int i = 0 ; i < n ; i ++){
		for(;a[j] + k <= a[i] ; j ++) ;
        //a[j] + k <= a[i]时j增加
        //当结束时说明找到了所有满足条件的最大的
        //排过序，所以 aj 以下都同时成立
        //j不用归零，下一次直接接着这一次
		ans += j ;
        //排过序后，若a[j] + k <= a[i] 
        //则 a[j - 1] + k <= a[i] 以此类推，a1 - aj 共j个都可以
	}
	printf("%lld",ans) ; 
	return 0;//感觉语言不行，欢迎评论补充
}

100分题解

运用二分查找

#include
using namespace std;
long long n,k,a[500001],sum,l,r,mid,ans;
int main()
{
    cin >> n >> k;
    for (int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    sort (a + 1,a + n + 1);
    for (int i = 1;i < n;i++)
    {
        l = i;
        r = n;
        ans = 0;
        while (l <= r)
        {
            mid = (l + r) / 2;
            if (a[mid] >= a[i] + k)
            {
                r = mid - 1;
                ans = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        if (ans)
        {
            sum += n - ans + 1;
        }
    }
    cout << sum;
    return 0;
}

这道题刚开始我也没有什么思路，上来就暴力，双重循环直接爆 O(N²)。 因为这题数据比较极端（改造样例 × 随机生成 √），所以暴力肯定是不行的。注意10⁶的数据范围，即使数据UPDATE了也会严重超时 那么怎么降呢？ 时间复杂度：O(N*logN) 事实上，O(N²)的循环很大一部分浪费在了极端接近的数据里，所以可以sort+暴搜，前区间（暂且称呼排序前小于等于a[i]-k的区间为前区间，尾区间同理，下文均如此描述）暴搜超限直接跳到尾区间。看上去挺不错不是吗/doge 但是！你想的太完美了。 该算法时间：O(logN+N²) 比暴力还慢。呵呵。 所以，暴搜再优化，翻成二分。这也是AC方法之一，尽管UPDATE之前会爆。这里要特别注意lower_bound和upper_bound的区别，题目是大于等于号！！自己思考要用哪个 这种方法生成的结果是有重叠的，要/2。 得，到这地步也没什么可优化的了，直接上代码。 由于本题解发于当天，不提供完整代码，第二天可以提供补全后的代码。由于代码习惯，部分变量表示可能不同于题目。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,a[1000009];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(ll j=0;j<n;j++){
        cin>>a[j];
    }
    ____ (1) ____;
    ll s=0;
    for(ll j=0;j<n;j++){
        s+=(____ (2) ____(a,a+n,a[j]-k)-a)+(____ (3) ____(a,a+n,a[j]-k)-a);
    }
    cout<<____ (3) ____;
    return 0;
}

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
} 

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。