题目描述
给定三个整数数组
A=[A1,A2,…AN],B=[B1,B2,…BN],C=[C1,C2,…CN]
请你统计有多少个三元组 (i,j,k)满足:
1≤i,j,k≤N
Ai<Bj<Ck
输入格式:第一行包含一个整数 N。第二行包含N个整数A1,A2,…AN
。第三行包含 N个整数B1,B2,…BN。第四行包含N个整数C1,C2,…CN。
输出格式
一个整数表示答案。
样例
blablabla
算法1
(二分+枚举)
过75%
C++ 代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a[N],b[N],c[N];
int ans=0;
int n;
signed find(int x,int q[])
{
int l=0,r=n-1;
while(l<r)
{
int mid=(l+r+1)/2;
if(q[mid]>=x) r=mid-1;
else l=mid;
}
if(q[r]>=x) return -1;
return r;
}
signed main()
{
cin>>n;
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];
sort(a,a+n);sort(b,b+n);sort(c,c+n);
for(int i=n-1;i>=0;i--)
{
if(find(c[i],b)==-1) continue;
int x=find(c[i],b);
for(int j=x;j>=0;j--)
{
if(find(b[j],a)==-1) break;
int y=find(b[j],a);
ans+=y+1;
}
}
cout<<ans;
return 0;
}
算法2
(二分)
过100%数据
C++ 代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
int num[3][N];
int main() {
int n;
scanf("%d", &n);
for(int i = 0; i < 3; ++i)
for(int j = 1; j <= n; ++j)
scanf("%d", &num[i][j]);
for(int i = 0; i < 3; ++i)
sort(num[i]+1, num[i]+n+1);
LL ans = 0;
//枚举B,寻找A满足的个数以及C满足的个数相乘
for(int i = 1; i <= n; ++i) {
int key = num[1][i];
//A中二分查找第一个小于key的数的下标
int pos1 = lower_bound(num[0]+1, num[0]+n+1, key)-num[0]-1;
//C中二分查找第一个大于key的数的下标
int pos2 = upper_bound(num[2]+1, num[2]+n+1, key)-num[2];
if(pos1 >= 1 && pos2 <= n) {
ans += (LL)pos1*(n-pos2+1);
}
}
cout<<ans<<endl;
return 0;
}