题解：P1296 奶牛的耳语

LoyalSoldier · 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;
}