题目描述
给定三个整数数组
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。
输出格式
一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai,Bi,Ci≤105
输入样例:
3
1 1 1
2 2 2
3 3 3
输出样例:
27
算法1 前缀和
C++ 代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2e5;
int n;
int a[N],b[N],c[N];
int s[N],cnt[N];
int as[N],cs[N]; // as[i]表示在A[]中有多少个数小于b[i],cs[i]表示在C[]中有多少个数大于b[i]
//思路:前缀和 把a里面的数出现的次数记录一下,求a的前缀和,看b中有哪些数比a大,c同理
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
a[i]++;
}
for(int i=0;i<n;i++){
cin>>b[i];
b[i]++;
}
for(int i=0;i<n;i++){
cin>>c[i];
c[i]++;
}
//处理a
for(int i=0;i<n;i++) cnt[a[i]]++;
for(int i=1;i<N;i++) s[i]=s[i-1]+cnt[i];// 求cnt[]的前缀和
for(int i=0;i<n;i++) as[i]=s[b[i]-1];
//清空一下cnt[N]和s[N]
memset(s,0,sizeof s);
memset(cnt,0,sizeof s);
//处理c
for(int i=0;i<n;i++) cnt[c[i]]++;
for(int i=1;i<N;i++) s[i]=s[i-1]+cnt[i];
for(int i=0;i<n;i++) cs[i]=s[N-1]-s[b[i]];
// // 枚举每个b[i] 相乘 注意数字很大
long long ans=0;
for(int i=0;i<n;i++){
ans+=(long long)as[i]*cs[i];
}
cout<<ans<<endl;
return 0;
}
算法二 二分(还没尝试)
//思路:二分 先对三个数组进行sort排序,然后遍历b数组,对于b中的每一个数b[i],在a数组中寻找最后一个
//小于b[i]的数的下标,这里我们记做l.在再c数组中寻找第一个大于b[i]的数的下标,这里我们记做r
//可知a数组中,小于b[i]的数的个数为l+1,c数组中大于b[i]数的个数为n-r.(下标从0开始)
//因此在三元递增组中,以b[i]为中间数的个数为(l+1)*(n-r).
//遍历b数组,res+=(l+1)*(n-r) 即为答案
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) scanf("%d", &b[i]);
for (int i = 0; i < n; i++) scanf("%d", &c[i]);
sort(a, a + n); //二分需要满足单调性
sort(b, b + n);
sort(c, c + n);
LL res = 0; //答案可能会很大,会爆int
for (int i = 0; i < n; i++)
{
int l = 0, r = n - 1; //二分查找a数组中最后一个小于b[i]的数的下标
while (l < r)
{
int mid = (l + r + 1) / 2;
if (a[mid] < b[i]) l = mid;
else r = mid - 1;
}
if (a[l] >= b[i]) //如果未找到小于b[i]的数,将x标记为-1,后续计算时 x+1==0
{
l = -1;
}
int x = l;
l = 0, r = n - 1;
while (l < r)
{
int mid = (l + r) / 2;
if (c[mid] > b[i]) r = mid;
else l = mid + 1;
}
if (c[l] <= b[i]) //如果未找到大于b[i]的数,将y标记为n,后续计算时 n-y==0;
{
r = n;
}
int y = r;
res += (LL)(x + 1)*(n - y);
}
printf("%lld\n", res);
return 0;
}
作者:林小鹿
链接:https://www.acwing.com/solution/content/18628/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。