关于本题的一些疑惑解答【详细版】
首先代码先给出来,注释写的很详细。
y总的思路就是:
先说A(C和A的方法一样,就不赘述),用一个数组来统计各个数字出现的次数。
就是定址法。 再用一个前缀和,来统计每个小于等当前位置的所有的数的出现次数。
最后通过B的数的值来找到对应的前缀和,即找到了小于B的数出现的次数。
1.第一个问题: 为啥要统一加一?
统一加1的目的是为了防止数组越界。
2.第二个问题: 为啥前缀和的for 是从1~N
其实1~N指的是数据范围内 的前缀和。不要以为是 1~n,这只是我们数的个数,并不是数值的大小
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
int n;
int a[N],b[N],c[N];
int cnt[N],s[N];//统计个数 , 前缀和
int at[N],ct[N];//小于B的元素个数 大于B的元素个数
int main(void)
{
cin>>n;
for(int i=0;i<n;i++) scanf("%d",&a[i]),a[i]++;//统一加1,是为了避免数组越界
for(int i=0;i<n;i++) scanf("%d",&b[i]),b[i]++;
for(int i=0;i<n;i++) scanf("%d",&c[i]),c[i]++;
for(int i=0;i<n;i++) cnt[a[i]]++;//统计各个数字出现的个数
for(int i=1;i<N;i++) s[i]=s[i-1]+cnt[i];//统计每个数字出现次数的前缀和
for(int i=0;i<n;i++) at[i]=s[b[i]-1];//统计小于B的元素的个数
memset(cnt,0,sizeof cnt);
memset(s,0,sizeof s);
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++) ct[i]=s[N-1]-s[b[i]];
long long ans=0;
for(int i=0;i<n;i++) ans+=(long long)at[i]*ct[i];
cout<<ans<<endl;
return 0;
}