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;

}

同类题型

视频讲解

⬅️ 5、四平方和 🏠 00-刷题理模型 ➡️ sqrt(x)