【C++算法】洛谷P1102：A-B数对，思路，lower_bound，upper_bound，二分答案，代码详解

1）解题思路

• 这道题要求我们在序列中找到 A − B = C A-B=C A−B=C 的数对的个数，下标不同的数对算作不同的数对
• 如果采用常规做法就是两层循环，每个数字依次作为 B B B ，在从其之后的元素选出元素与之相减，看得到的结果是不是 C C C，是的话 a n s + + ans++ ans++ ，这是枚举的做法
• 我们不妨换一个思路，既然我们枚举每个数字作为 B B B，那么B就是确定的，题目中的 C C C 也是确定的， A − B = C A-B=C A−B=C 问题，我们就可以转换为 B + C = A B+C=A B+C=A 问题，对于每一个数字 B B B，我们在其之后的元素中，去找有多个元素恰好比 B B B 大 C C C 就可以了
• 如何快速的找到恰好比 B B B 大 C C C 的数字有多少个呢？我们只需要找到这个比 B B B 大 C C C 的数第一次出现的位置和最后一次出现的位置，这样两次位置的下标之差就是这个比 B B B 大 C C C 的数字出现的个数，为了快速找到这个数字，我们可以借助二分查找中的 l o w e r _ b o u n d ( ) lower\_bound() lower_bound() 函数 和 u p p e r _ b o u n d ( ) upper\_bound() upper_bound() 函数（注意，使用二分之前一定要保证数组有序哦！我们可以用 s o r t sort sort 快速排序， s o r t sort sort 的时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn) ）

• l o w e r _ b o u n d lower\_bound lower_bound 查找第一个大于等于某个元素的值，可以用来查找第一个比 B B B 大 C C C 的数的下标
• u p p e r _ b o u n d upper\_bound upper_bound 查找第一个大于某个元素的值，可以用来查找最后一个比 B B B 大 C C C 的数的下标，因为最后一个刚好比 B B B 大 C C C 的数，一定他的下一个数（数组是有序的），而我们用 l o w e r _ b o u n d lower\_bound lower_bound 找的就是最后一个刚好比 B B B 大 C C C 的数的下一个数，可结合下图理解

2）三种情况

• 第一种情况，对于 1   1   2   3   ( c = 1 ) 1\ 1\ 2\ 3\ (c=1) 1 1 2 3 (c=1) 的 1 1 1 这个元素，第一个 > = 1 + 1 >= 1+1 >=1+1 的元素是 2 2 2，而且这个 2 2 2 也找得到，第一个 > 1 + 1 > 1+1 >1+1 的元素是 3 3 3，而且这个 3 3 3 也找得到，那么二者的下标相减，就是 2 2 2 这个元素出现的次数，假如有多个 2 2 2 出现，那第一个 > 1 + 1 >1+1 >1+1 的元素的下标也往后移了，二者相减得到的还是 2 2 2 出现的次数
• 第二种情况，比如序列是 1   1   1   1   ( c = 1 ) 1\ 1\ 1\ 1\ (c=1) 1 1 1 1 (c=1)，对于 1 1 1 ，第一个 > = 1 + 1 >= 1+1 >=1+1 和 第一个 > 1 + 1 > 1+1 >1+1 的元素都找不到，**都找不到的话 l o w e r _ b o u n d lower\_bound lower_bound 和 u p p e r _ b o u n d upper\_bound upper_bound 返回的结果都是数组的最后一个元素再往后一个元素的地址，**那么二者相减就是 0 0 0 ，说明没有比 1 1 1 恰好大 1 1 1 的元素
• 第三种情况，比如序列是 1   1   2   3   ( c = 1 ) 1\ 1\ 2\ 3\ (c=1) 1 1 2 3 (c=1) 的 2 2 2 这个元素，第一个 > = 2 + 1 >=2+1 >=2+1 的元素是 3 3 3，下标是 4 4 4（假设我们从 1 1 1 开始存），第一个 > 2 + 1 >2+1 >2+1 的元素在数组中找不到，因为最大就是 3 3 3 ，那么这个时候函数的返回值就会停在数组的最后一个元素再往后一个元素的地址呀？，二者相减得到 1 1 1，比 2 2 2 恰好大 1 1 1 的元素只有 3 3 3 这一个元素

3）代码

• 附带了两种做法，第一种做法做法是 l o w e r _ b o u n d lower\_bound lower_bound 和 u p p e r _ b o u n d upper\_bound upper_bound 通过库函数来实现的

• 第二种做法是手写二分去找这两个元素的下标的做法
• 还有因为组合数太多啦，所以对于最终结果需要开 l o n g   l o n g long\ long long long

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=1e6+5;
ll arr[N];

int main() {
	// 先试试加快输入输出有没有用
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,diff;
	cin>>n>>diff;
	
	for(ll i=1;i<=n;i++) {
		cin>>arr[i];
	}
	ll cnt=0;
	// O(n2)无法通过,用双指针或者二分
	sort(arr+1,arr+n+1); // 排序,这样减出来才是正数
	for(ll i=1;i<=n;i++) {
		// 用二分查找去找arr中第一个大于等于arr[i]+diff的第一个元素
		ll left=lower_bound(arr+1,arr+n+1,arr[i]+diff)-arr; 
		cout<<left<<' ';
		// 用二分查找去找arr中第一个大于arr[i]+diff的第一个元素
		ll right=upper_bound(arr+1,arr+n+1,arr[i]+diff)-arr;
		cout<<right<<' ';
		cnt+=right-left;
		cout<<endl;
	}
	cout<<cnt<<endl;
	
	cout<<"--------------";
	cout<<endl;
	
	cnt=0;
	
	ll l,r;
	ll ans1,ans2;
	// 用普通二分来做,不借助库函数的话应该是
	for(ll i=1;i<=n;i++) {
		// 找arr中第一个大于等于arr[i]+diff的元素
		l=1,r=n+1;
		while(l<r) {
			int mid=l+r>>1;
			if(arr[mid]>=arr[i]+diff) {
				r=mid;
			} else {
				l=mid+1;
			}
		}
		ans1=l;
		cout<<ans1<<' ';
		// 找arr中第一个大于arr[i]+diff的元素
		l=1,r=n+1;
		while(l<r) {
			int mid=l+r>>1;
			if(arr[mid]>arr[i]+diff) {
				r=mid;	
			} else {
				l=mid+1;
			}
		}
		ans2=l;
		cout<<ans2<<' ';
		cout<<endl;
		cnt+=ans2-ans1;
	}	
	cout<<cnt;
	return 0;
}