自动搬运

查看原文

来自洛谷，原作者为

	ylzpl ​ | 最后在线时间: 2025/8/24 21:22

搬运于2025-08-24 21:23:28，当前版本为作者最后更新于2025-05-17 10:29:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本题难度：橙。
考查算法：二分。
题目意思已经很清晰了，那么我们讲两种思路。

• 暴力法：对于每一个 $a_i$，找到所有的 $a_j$，其中 $1≤j≤n,j≠i$，如果 $a_i-d≤a_j≤a_i+d$，就找到一对。
• 二分法：我们在这里需要引入一个函数：upper_bound。这个函数可以找到第一个比 $x$ 大的数，写法：upper_bound(a+1,a+1+n,x)-a。这里减 $a$ 的原因是前面的函数会返回一个地址，减掉 $a$ 的地址（也就是 $a_0$）的位置，就可以求出下标。那么在本题当中，我们对于每一个 $a_i$，用函数找出第一个比 $a_i+d$ 大的，在减去 $i+1$，那么剩下的一段就可以跟 $a_i$ 组成一对。注意：这里的函数找的是比 $a_i+d$ 大的数，而我们要找的是 $a_i-d≤a_j≤a_i+d$，所以要先减一，求出小于等于的，在减去前面 $i$ 个（自己不算）。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
int n,k;
int a[maxn];
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
	    cin>>a[i];
	}
	sort(a+1,a+1+n);
	int ans=0;
    for(int i=1;i<=n;i++){
        ans+=upper_bound(a+1,a+1+n,a[i]+k)-a-i-1;
    }
    cout<<ans;
	return 0;
}