博客

P1102 A-B 数对 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

方法一：桶排序（map映射）

思路：由A-B=C知，A-C=C，转换思路知，我们可以求原数组中有多少个满足条件的B，因此我们先 每个数A的个数先统计出来，然后A-C，最后统计原数组中满足条件的B的个数，即原数组中有多少个A-C

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll a[N], sum = 0;
map<int, int>mp;

int main() {
	ll n, c;
	cin >> n >> c;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		mp[a[i]]++;
		   a[i] -= c;
	}
	for (int i = 0; i < n; i++)
		sum += mp[a[i]];
	cout << sum;
	return 0;
}

方法二：二分

思路：先将数组按单调递增的方式排序，然后用L遍历该数组，再用两个双指针r1,r2,找满足A-L=C的区间，即r2停在a[i]-L<C的下一个数的位置，r2停在a[i]-L<=C的下一个数的位置，则如果(r2,r1)区间内的数均能满足a[i]-L=C,则将改区间数的个数加到ans上去

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll a[N];
int main() {
	ll n, c, ans = 0;
	cin >> n >> c;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
		sort(a+1,a+1+n);//排序，使其成单调上升的形式
	ll l = 1, r1 = 1, r2 = 1;//l用来遍历数组中的数，r1,r2来找满足条件的区间
	for (; l <= n; l++) {
		while (r1 <= n && a[r1] - a[l] <= c)
			r1++;
		while (r2 <= n && a[r2] - a[l] < c)
			r2++;
		if (a[r2] - a[l] == c && a[r1 - 1] - a[l] == c && r1 - 1 >= 1)
			ans += r1 - r2;
	}
	cout << ans << endl;
	return 0;
}

方法三：stl的二分函数

lower_bound(a,a+n,x)-a       //下标从0开始

lower_bound(a+1,a+1+n,x)-a             //下标从1开始

找到最小的a数组的下标i,满足a[i]>=x

upper_bound(a,a+n,x)-a           //下标从0开始

upper_bound(a+1,a+1+n,x)-a          //下标从1开始

找到最小的a数组的下标i,满足a[i]>x

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll a[N];
int main() {
	ll n, c, ans = 0;
	cin >> n >> c;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++) {
		ans += (upper_bound(a + 1, a + 1 + n, a[i] + c) - a ) - (lower_bound(a + 1, a + n + 1, a[i] + c ) - a);
	}
	cout << ans << endl;
	return 0;
}