文章
36
粉丝
505
获赞
55
访问
370.5k
这道题我看了过了的那两个老哥的做法,发现竟然暴力枚举过了???只能说这题数据很水。。
正解:这道题等价于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);
...
登录后发布评论
大哥你第二个代码写错了 结果不对
大哥你第二个代码写错了 结果不对
两个二分减就是一样的数个数吧