第九届蓝桥杯【C++省赛B组】【第六题：递增三元组】——二分解法（附解题代码）

本文主要是介绍第九届蓝桥杯【C++省赛B组】【第六题：递增三元组】——二分解法（附解题代码），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

给定三个整数数组

A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],

请你统计有多少个三元组 (i,j,k) 满足：
1）1≤i,j,k≤N
2）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

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int a[N],b[N],c[N];
int lower(int *p,int l,int r,int x){//找出第一个大于或等于x的元素位置 
	/* 
	在 1 2 3 4 6 8 9中lower 当 x = 5 返回的是 6的位置
	推导：当l=r-1时,mid = (r-1+r)>>1 = r-1 = l,所以p[mid(l)]<x 推导出l = mid+1 = r。  
	
	在 1 2 3 4 5 5 5 5 6 8 9中upper 当 x = 5 返回的是最左边5的位置（因为当等于x时是r在移动） 
	*/
	int n = r;
	if(p[n]<x) return n+1; //若在最右边的数p[n]仍然小于x，即整个序列都应是小于x的。 
	if(p[l]>=x) return 0; // 不存在小于x的数 
	while(l<r){ //整数二分 
		int mid = l+r>>1;
		if(p[mid] >= x) r = mid;
		else l = mid+1;
	}
	return l; //获得的是第一个大于等于x的数的位置 
}

int upper(int *p,int l,int r,int x){//找出第一个大于x的元素位置 
	/*
	在 1 2 3 4 6 8 9中upper 当 x = 5 返回的是4的位置 
	推导：当l=r-1时,mid = (r-1+r+1)>>1 = r,所以p[mid(r)]>x 推导出r = mid-1 = l。  
	
	在 1 2 3 4 5 5 5 5 6 8 9中upper 当 x = 5 返回的是最右边5的位置（因为当等于x时是l在移动）
	*/
	int n = r;
	if(p[l] > x) return 0;  //若在最左边的数p[l]大于x，即整个序列都应是大于x的。
	if(p[n] <= x) return n+1; //不存在大于x的数 
	while(l<r){ //整数二分 
		int mid = l+r+1>>1;
		if(p[mid] > x) r = mid - 1;
		else l = mid;
	}
	
	return l+1; //获得的是第一个大于x的数的位置 
}

int main(){
	int n;
	long long res=0;
	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 = 0; i < n; i++){
		int x = lower(a,0,n-1,b[i]);  //在有序序列中找出第一个大于或等于b[i]的元素位置 
		int y = upper(c,0,n-1,b[i]); //在有序序列中找出第一个大于b[i]的元素位置 
		res += 1LL*x*(n-y); //n-1-y+1 = n-y 
	}
	cout<<res;
	return 0;
}

这篇关于第九届蓝桥杯【C++省赛B组】【第六题：递增三元组】——二分解法（附解题代码）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！