当前位置：首页 > news >正文

A-B数对（二分查找）

news 2025/7/9 21:27:29

#include<bits/stdc++.h>
using namespace std;using ll = long long;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,c;cin>>n>>c;int nu[200000];for(int i=0;i<n;i++){cin>>nu[i]; // 输入数组元素}sort(nu,nu+n);ll cnt=0; // 统计满足条件的数对数量for(int i=0;i<n;i++){ll a=nu[i]+c;int l=0,r=n-1;ll ans=n; // 初始设为数组长度（表示未找到）while(l<=r){int mid=l+(r-l)/2;if(nu[mid]>=a){ans=mid;r=mid-1;}else{l=mid+1;}}l=0,r=n-1;ll res=-1; // 初始设为 -1（表示未找到）while(l<=r){int mid=l+(r-l)/2;if(nu[mid]>a){r=mid-1;} else{res=mid;l=mid+1;}}if(ans<=res){cnt+=res-ans+1;}}cout<<cnt;return 0;}

输入数组 nu 并对其排序，方便后续通过二分查找快速定位数值。

遍历数组中的每个元素 nu[i]，计算目标值 a = nu[i] + c，即寻找数组中大于或等于 a 的第一个位置（起始点）和小于或等于 a 的最后一个位置（结束点）。

两次二分查找：

第一次二分查找：找到数组中第一个大于等于 a 的位置。
第二次二分查找：找到数组中最后一个小于等于 a 的位置。
两次查找的结果分别是 ans 和 res。

数对的数量为区间长度 res - ans + 1

使用 lower_bound 和 upper_bound:

#include<bits/stdc++.h>
using namespace std;using ll = long long;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,c;cin>>n>>c;int nu[200000];for(int i=0;i<n;i++){cin>>nu[i];}sort(nu,nu+n);ll cnt=0;for(int i=0;i<n;i++){ll a=nu[i]+c;ll ans=lower_bound(nu,nu+n,a)-nu;ll res=upper_bound(nu,nu+n,a)-nu-1;if(ans<=res){cnt+=res-ans+1;}}cout<<cnt;return 0;}

lower_bound(nu, nu + n, a) 返回的是第一个大于或等于 a 的元素的迭代器。

upper_bound(nu, nu + n, a) 返回的是第一个大于 a 的元素的迭代器。由于我们需要找的是小于或等于 a 的最大值，因此在计算 res 时，需要减去 1。