第九届蓝桥杯第六题：递增三元数组二分-白红宇

第九届蓝桥杯第六题：递增三元数组二分

阅读量：3905 次

发布时间：2019-05-23

本文共 714 字，大约阅读时间需要 2 分钟。

标题：递增三元组

给定三个整数数组

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。

对于30%的数据，1 <= N <= 100

对于60%的数据，1 <= N <= 1000

对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000

【输出格式】

一个整数表示答案

【样例输入】

1 1 1

2 2 2

3 3 3

【样例输出】

将a和c序列排序。

遍历b序列，二分查找a中比b[i]小的元素，c中比b[i]大的元素。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;const int maxn=1e5+5;int n;int num[3][maxn];int sum[3][maxn];int a[3][maxn];int main(){	ll ans=0;	scanf("%d",&n);	for (int i=0;i<3;i++)	{		for (int j=0;j