蓝桥杯 二分查找 or 前缀和
此题可以一题多解,下面是用 stl 的二分查找
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
int N;
cin >> N;
vector<int>a(N, 0);
vector<int>b(N, 0);
vector<int>c(N, 0);
for (int i = 0; i < N; i++) {
cin >> a[i];
}
for (int i = 0; i < N; i++) {
cin >> b[i];
}
for (int i = 0; i < N; i++) {
cin >> c[i];
}
// 排序后以 b 数组为基准,遍历 b 并分别对 ac 进行二分查找
// 答案累加 a 中小于 b[i] 的数量乘以 c 中大于 b[i] 的数量
sort(a.begin(), a.end());
// sort(b.begin(), b.end());
sort(c.begin(), c.end());
long long ans = 0;
// lower_bound 返回的是迭代器,进行迭代器的加减
for (auto &i : b) {
// lower_bound 返回第一个小于等于 i 的元素的迭代器,和第一个元素的迭代器相减正是数量
// lower_bound 返回第一个小于等于 i 的元素的迭代器,和数组结束(无元素)相减是数量
auto maxInA = lower_bound(a.begin(), a.end(), i);
auto minInB = upper_bound(c.begin(), c.end(), i);
// 注意要开 long long
long long sizeA = maxInA - a.begin();
long long sizeB = c.end() - minInB;
ans += sizeA * sizeB;
}
cout << ans;
return 0;
}