文章

36

粉丝

505

获赞

55

访问

370.5k

头像
题解:A-B数对
P1599
发布于2020年3月23日 00:50
阅读数 10.8k

这道题我看了过了的那两个老哥的做法,发现竟然暴力枚举过了???只能说这题数据很水。。

正解:这道题等价于A+C=B,枚举每个A,看B在不在数组里。

如何看B在不在数组里?遍历?太慢了!

这里用二分的方法来查找数组里首次出现B的位置,再查找B结束的位置,两位置之差+1就是B的个数,答案加上就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, c, a[200100], ans;
int findl(LL x, LL l, LL r)//寻找初始位置
{
	while (r - l >= 5)//二分怕出错,最后留下长度很小的区间然后遍历
	{
		LL m = (l + r) / 2;
		if (x <= a[m])
			r = m;
		else
			l = m + 1;
	}
	for (int i = l; i <= r; i++)//遍历剩下的区间
		if (a[i] == x)
			return i;
	return -1;//找不到B那么返回-1
}
int findr(LL x, LL l, LL r)//同上
{
	while (r - l >= 5)
	{
		LL m = (l + r) / 2;
		if (x >= a[m])
			l = m;
		else
			r = m - 1;
	}
	for (int i = r; i >= l; i--)
		if (a[i] == x)
			return i;
	return -1;
}
int main()
{
	cin >> n >> c;
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++)
	{
		LL t = a[i] + c, posl, posr;
		posl = findl(t, 1, n);
	...
登录查看完整内容


登录后发布评论

4 条评论
chenziyi VIP
2020年5月8日 21:17

大哥你第二个代码写错了 结果不对

赞(0)

mzymzyo : 回复 chenziyi: sorry,小错误。第十行应该是for (int i = 1; i <= n; i++)

2020年5月9日 05:11
chenziyi VIP
2020年5月8日 21:17

大哥你第二个代码写错了 结果不对

赞(0)
chenziyi VIP
2020年5月8日 21:14

两个二分减就是一样的数个数吧

赞(0)