题解：P1296 奶牛的耳语

· · 题解

前言

在我和好友 UCPP 的热血沸腾的组合技之后，这道题所有题解都被我们叉了，所以抓紧补一篇题解。

题解

先来想暴力做法，再考虑如何优化。

暴力做法非常简单，枚举每一对奶牛（记作奶牛 i 和奶牛 j），只要比较这两头奶牛的距离 \left | p_i-p_j \right | 和 d 的大小即可。时间复杂度 O(n^2)，显然超时。

考虑优化。我们发现，在我们对 p 数组排序后，对于每头奶牛（记作奶牛 i），它后面的所有奶牛离它的距离 p_j-p_i(i<j \le n) 肯定是逐渐增加的。换而言之，对于每头奶牛 i，我们只要找出满足 i <j \le n 且 p_j-p_i\le d 的 j 的数量即可。答案具有单调性，考虑二分。

手写二分太过麻烦。在 C++ 的 STL 中，有一个很好用的函数：upper_bound。它可以找出在一个有序的数组中大于给定值的第一个元素。举个例子，在数组 a=\{1,1,4,5,14\} 中想要查找第一个大于 4 的数，代码可以写为 int id=upper_bound(a,a+5,4)-a;。其中 id 的值就是 5 的下标，也就是 3。

以上算法的时间复杂度为 O(n \log n)，瓶颈在排序和二分部分。

本题还有一个坑：如果数据到达极限，共 10^6 头奶牛，相邻两头奶牛的 p 值也是相邻的，这样答案大约是 10^{10}，int 会爆。

学会了这些，代码就能轻松写出了。

代码

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n,d;
int a[1000005];
ll ans=0;
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>d;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        int x=upper_bound(a+i+1,a+n+1,a[i]+d)-a;
        ans+=x-i-1;
    }
    cout<<ans<<endl;
    return 0;
}
/*
---INFORMATIONS---
TIME:2025-05-14 13:02:02
PROBLEM:P1296
CODE BY __CrossBow_EXE__ Luogu uid967841
*/