AcWing 5077. 差分计数
原题链接
简单
作者:
小蝴蝶
,
2024-07-26 16:30:04
,
所有人可见
,
阅读 6
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, B = N * 2;
int n, x;
int a[N];
int w[N * 4];
int main()
{
scanf("%d%d", &n, &x);
for(int i = 0; i < n; i ++)
{
scanf("%d", &a[i]);
}
long long res = 0;
// 题目中的注意即是提示也是陷阱,
// 相同时 a[i] - a[j] = 0,为 x 的特殊情况
// 此时配对情况如下:
/**
* 0 0
* 1 1
* 2 2
* 3 3
* 4 4
* 5 5
*
*/
// x = 0 时,i = idx 与 j = idx 下标对只能记录一次
// x = 其它时,i = idx 与 i = idx 不会是答案
for(int i = 0; i < n; i ++)
{
// 枚举 j
// a[i] - a[j] = x
int y = a[i] + x;
res += w[y + B];
w[a[i] + B] ++; // *
}
memset(w, 0, sizeof w);
for(int i = n - 1; i >= 0; i --)
{
// 枚举 j
// a[i] - a[j] = x
w[a[i] + B] ++; // *
int y = a[i] + x;
res += w[y + B];
}
printf("%lld", res);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, B = N * 2;
int n, x;
int a[N];
int w[N * 4];
int main()
{
scanf("%d%d", &n, &x);
for(int i = 0; i < n; i ++)
{
scanf("%d", &a[i]);
w[a[i] + B] ++;
}
long long res = 0;
// 枚举到某一个数时将其作为 j,枚举其他数时其作为 i
for(int i = 0; i < n; i ++)
{
int y = a[i] + x;
res += w[y + B];
}
printf("%lld", res);
return 0;
}