5、递增三元组
题目 递增三元组
思路分析
1、三个排序
2、对于每一个b 找比他小的a的数量 比他大的c的数量 相乘
3、相加
靠 这题忘了开LL 少过两个案例 逻辑想完了后要多检查一下这些东西啊
嘶 好像也检查不到 要不每次直接开大点？一般也不会卡这点空间？？？
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL a[N],b[N],c[N];
int n;
int 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);
LL sum=0;
for(int i=0;i<n;i++){
int x=b[i];
int l=0,r=n;
while(l<r){
int m=l+r>>1;
if(a[m]>=x)//找到第一个不小于x的数 它的下标-0就是小于x的数量
r=m;
else
l=m+1;
}
int cnt_a=r;
l=0,r=n;
while(l<r){
int m=l+r>>1;
if(c[m]>x)//找到第一个大于x的数 n-r就是大于x的数量
r=m;
else
l=m+1;
}
LL cnt_b=n-r;
sum+=cnt_a*cnt_b;
}
cout<<sum;
return 0;
}
💬 评论