本题的暴力做法可以过掉一多半的测试用例,那个复杂度是n的3次方/ 或者是通过b数组来查找a和c数组中满足要求的数值复杂度为n的2次方。还是会TLE,那就要用到nlogn 的复杂度。
可以用二分来查找。注意在查找的时候右边界值的处理,先将a和c数组进行排序预处理,判断边界值:如果a数组中的最小值还要大于等于b数组中的当前元素那么将数量置为0,如果b数组的最大值还要小于等于b数组的值的时候那么将数量置为n+1;其他情况正常二分即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N],b[N],c[N];
int n;
int main(){
scanf("%d",&n);
LL res = 0;
for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
for(int i = 1;i <= n;i++) scanf("%d",&b[i]);
for(int i = 1;i <= n;i++) scanf("%d",&c[i]);
sort(a+1,a+n+1);
// sort(b,b+n);
sort(c+1,c+n+1);
// for(int i = 1;i <= n;i++) {
// cout<<a[i]<<" ";
// }
// cout<<endl;
for(int i = 1;i <= n;i++) {
int s1 = 0,s2 = 0;
int l1 = 1,r1 = n;
while(l1 < r1){
if(a[l1] >= b[i]) {
l1 = 0;
break;
}
int mid = l1 + r1 + 1 >> 1;
if(a[mid] < b[i]) l1 = mid;
else r1 = mid - 1;
}
int l2 = 1,r2 = n;
while(l2 < r2){
if(c[r2] <= b[i]){
l2 = n+1;
break;
}
int mid = l2 + r2 >> 1;
if(c[mid] > b[i]) r2 = mid;
else l2 = mid + 1;
}
// cout<<l1<<" "<<n-l1+1<<" ";
// 这里计算结果的时候要进行类型转换 不然最后一个数据过不了
res += (LL)l1*(n-l2+1);
// cout<<res<<endl;
}
// for(int i = 1;i <= n;i++) {
// for(int j = 1;j <= n;j++) {
// for(int k = 1;k <= n;k++) {
// if(a[i] < b[j]&& b[j] < c[k]){
// res ++;
// }
// }
// }
// }
cout<<res<<endl;
return 0;
}