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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了第九届蓝桥杯【C++省赛B组】【第六题：递增三元组】——二分解法（附解题代码），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1977字，纯文字阅读大概需要3分钟。

内容图文

给定三个整数数组

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组】【第六题：递增三元组】——二分解法（附解题代码）全部内容，希望文章能够帮你解决第九届蓝桥杯【C++省赛B组】【第六题：递增三元组】——二分解法（附解题代码）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端