三数比较
题目描述
给定三个长度为 $n$ 的数组 $a, b, c$,求有多少组 $(i, j, k)$ 满足 $1 \leq i, j, k \leq n$ 且 $a_i < b_j < c_k$
数据范围
对于 $30\%$ 的数据,$1 \leq n \leq 100$
对于 $60\%$ 的数据,$1 \leq n \leq 2000$
对于 $100\%$ 的数据,$1 \leq n \leq 2 \times 10^5, 1 \leq a_i, b_i, c_i \leq 10^9$
题解
30 pts
考虑直接暴力,枚举三个数组三个数。
时间复杂度:$O(n^3)$。
60 pts
对第三个数组排序,枚举前两个数,并对第三个数组进行二分。
时间复杂度:$O(n^2\log n)$。
100pts
考虑到直接排 $b$ 数组然后二分,第二个数依然不确定,无法计算个数。
可以先排序,考虑到对于 $a_i$,满足的 $b_j$(在排序后)是后缀的,就可以上后缀和。
时间复杂度:$O(n\log n)$
完整代码,时间复杂度:$O(n\log n)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N], b[N], c[N];
long long s[N];
long long get(int x) {
long long l = 1, r = n;
while (l < r) {
long long mid = l + r >> 1;
if (c[mid] <= x) l = mid + 1;
else r = mid;
}
if (c[l] <= x) l = n + 1;//如果没有满足要求的,就是直接0
return n - l + 1;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ )
cin >> a[i];
for (int i = 1; i <= n; i ++ )
cin >> b[i];
for (int i = 1; i <= n; i ++ )
cin >> c[i];
sort(b + 1, b + n + 1);
sort(c + 1, c + n + 1);
for (int i = n; i; i -- )
s[i] = s[i + 1] + get(b[i]);
long long ans = 0;
for (int i = 1; i <= n; i ++ ) {
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (b[mid] <= a[i]) l = mid + 1;
else r = mid;
}
if (b[l] <= a[i]) l = n + 1; //这里也要特判一下,如果没有满足要求的就是0
ans += s[l];
}
cout << ans << endl;
return 0;
}