题目链接
题目大意
给定三个数组 $A, B, C$,以及一个非负整数 $d$。
求共有多少个三元组 $(i, j, k)$,满足:$|A_i - B_j| \le d, |A_i - C_k| \le d, |B_j - C_k| \le d$。
解题思路
双指针常用于解决计数类问题。
如果把 $A,B,C$ 三个数组合并到一个数组 $D$ 中,并将 D 数组排序,问题就转化为求所有满足 $D[j] - D[i]$ 的区间中能选出多少个 $A, B, C$;考虑到直接枚举区间的时间复杂度较高,而 D 数组具有单调性,因此可以使用双指针中的快慢指针来选择区间。
算法流程
还没写~
Code
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <utility>
const int MAXN = 300010;
typedef std::pair<int, int> PII;
typedef long long ll;
#define val first
#define id second
int n, d, cnt[3][MAXN];
PII D[MAXN];
void prework()
{
std::sort(D + 1, D + n + 1);
for (int i = 0; i < 3; i ++ )
for (int j = 1; j <= n; j ++ )
cnt[i][j] = cnt[i][j - 1] + (D[j].id == i);
}
void solve()
{
int last = -1; // 上一次快指针的位置。
ll res = 0;
for (int i = 1, j = 1; i <= n; i ++ )
{
while (j <= n && D[j].val - D[i].val <= d) j ++ ;
if (j > last)
{
int cnta = cnt[0][j - 1] - cnt[0][i - 1];
int cntb = cnt[1][j - 1] - cnt[1][i - 1];
int cntc = cnt[2][j - 1] - cnt[2][i - 1];
res += (ll)cnta * cntb * cntc;
}
if (i <= last && last < j)
{
int cnta = cnt[0][last - 1] - cnt[0][i - 1];
int cntb = cnt[1][last - 1] - cnt[1][i - 1];
int cntc = cnt[2][last - 1] - cnt[2][i - 1];
res -= (ll)cnta * cntb * cntc;
}
last = j;
}
printf("%lld\n", res);
}
int main()
{
int l1, l2, l3, x;
scanf("%d%d%d%d", &l1, &l2, &l3, &d);
for (int i = 0; i < l1; i ++ )
{
scanf("%d", &x);
D[++ n] = std::make_pair(x, 0);
}
for (int i = 0; i < l2; i ++ )
{
scanf("%d", &x);
D[++ n] = std::make_pair(x, 1);
}
for (int i = 0; i < l3; i ++ )
{
scanf("%d", &x);
D[++ n] = std::make_pair(x, 2);
}
prework();
solve();
return 0;
}